fork download
  1. /*input
  2. 1
  3. 5 4
  4. abccba
  5. abddba
  6. xa
  7. abdcba
  8. aneverknow
  9. 1
  10. 2
  11. 4
  12. 3
  13. */
  14. #include <bits/stdc++.h>
  15. using namespace std;
  16. #pragma GCC optimize ("O3")
  17. typedef long long ll;
  18. typedef long double ld;
  19. int kiek[101010];
  20. int NXT[101010][26];
  21. int ans[101010];
  22. int main()
  23. {
  24. for (int t = 0; t < 101010; t++)
  25. {
  26. kiek[t] = ans[t] = 0;
  27. for (int d = 0; d < 26; d++)
  28. NXT[t][d] = -1;
  29. }
  30. ios_base::sync_with_stdio(false);
  31. cin.tie(0);
  32. int t;
  33. cin >> t;
  34. while (t--)
  35. {
  36. int num = 1;
  37. int n, q;
  38. cin >> n >> q;
  39. while (n--)
  40. {
  41. string s;
  42. cin >> s;
  43. int kur = 0;
  44. for (int i = s.size() - 1; i >= 0; i--)
  45. {
  46. int k = s[i] - 'a';
  47. if (NXT[kur][k] == -1)
  48. NXT[kur][k] = num++;
  49. kur = NXT[kur][k];
  50. ans[s.size() - i] = max(ans[s.size() - i], ++kiek[kur]);
  51. }
  52. }
  53. while (q--)
  54. {
  55. int x;
  56. cin >> x;
  57. cout << ans[x] << '\n';
  58. }
  59. for (int t = 0; t <= num; t++)
  60. {
  61. kiek[t] = ans[t] = 0;
  62. for (int d = 0; d < 26; d++)
  63. NXT[t][d] = -1;
  64. }
  65. }
  66. }
Success #stdin #stdout 0.01s 13948KB
stdin
Standard input is empty
stdout
Standard output is empty