fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 1e5 + 5;
  6. const int MAXCHAR = 26;
  7.  
  8. struct Vertex {
  9. int next[MAXCHAR], go[MAXCHAR];
  10. int leaf = -1;
  11. int p = -1;
  12. char pch;
  13. int link = -1, leaflink = -1;
  14.  
  15. Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
  16. fill(begin(next), end(next), -1);
  17. fill(begin(go), end(go), -1);
  18. }
  19. };
  20.  
  21. vector<Vertex> trie(1);
  22.  
  23. void add_string(string const &s, int idx) {
  24. int v = 0;
  25. for (char ch : s) {
  26. int c = ch - 'a';
  27. if (trie[v].next[c] == -1) {
  28. trie[v].next[c] = trie.size();
  29. trie.emplace_back(v, ch);
  30. }
  31. v = trie[v].next[c];
  32. }
  33. trie[v].leaf = idx;
  34. }
  35.  
  36. int go(int v, char ch);
  37.  
  38. int get_link(int v) {
  39. if (trie[v].link == -1) {
  40. if (v == 0 || trie[v].p == 0)
  41. trie[v].link = 0;
  42. else
  43. trie[v].link = go(get_link(trie[v].p), trie[v].pch);
  44. get_link(trie[v].link); //
  45. trie[v].leaflink = (trie[trie[v].link].leaf != -1) ? trie[v].link : trie[trie[v].link].leaflink;
  46. }
  47. return trie[v].link;
  48. }
  49.  
  50. int go(int v, char ch) {
  51. int c = ch - 'a';
  52. if (trie[v].go[c] == -1) {
  53. if (trie[v].next[c] != -1)
  54. trie[v].go[c] = trie[v].next[c];
  55. else
  56. trie[v].go[c] = v == 0 ? 0 : go(get_link(v), ch);
  57. }
  58. return trie[v].go[c];
  59. }
  60.  
  61. string S;
  62. int N;
  63. int K[MAXN];
  64. string M[MAXN];
  65. vector<int> results[MAXN];
  66.  
  67. int main() {
  68. ios::sync_with_stdio(0);
  69. cin.tie(0);
  70. cin >> S;
  71. cin >> N;
  72. for (int i = 0; i < N; i++) {
  73. cin >> K[i];
  74. cin >> M[i];
  75. add_string(M[i], i);
  76. }
  77. for (int i = 1; i < trie.size(); i++) //
  78. get_link(i); //
  79. int v = 0;
  80. for (int i = 0; i < S.size(); i++) {
  81. v = go(v, S[i]);
  82. int cur = v;
  83. while (cur != -1) {
  84. if(trie[cur].leaf != -1) //
  85. results[trie[cur].leaf].push_back(i);
  86. cur = trie[cur].leaflink;
  87. }
  88. }
  89. for (int i = 0; i < N; i++) {
  90. int minLength = 1 << 30;
  91. for (int j = K[i]; j <= results[i].size(); j++) {
  92. minLength = min(minLength, results[i][j - 1] - results[i][j - K[i]]);
  93. }
  94. if (minLength == 1 << 30) {
  95. cout << -1 << endl;
  96. } else {
  97. cout << minLength + M[i].size() << endl;
  98. }
  99. }
  100. }
Success #stdin #stdout 0.01s 8604KB
stdin
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
stdout
3
4
4
-1
5