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];
  10. int leaf = -1;
  11. int p = -1;
  12. char pch;
  13. int link = -1;
  14. int leaflink = -1;
  15. int go[MAXCHAR];
  16.  
  17. Vertex(int p = -1, char ch = '$') : p(p), pch(ch) {
  18. fill(begin(next), end(next), -1);
  19. fill(begin(go), end(go), -1);
  20. }
  21. };
  22.  
  23. vector<Vertex> trie(1);
  24.  
  25. void add_string(string const &s, int idx) {
  26. int v = 0;
  27. for (char ch : s) {
  28. int c = ch - 'a';
  29. if (trie[v].next[c] == -1) {
  30. trie[v].next[c] = trie.size();
  31. trie.emplace_back(v, ch);
  32. }
  33. v = trie[v].next[c];
  34. }
  35. trie[v].leaf = idx;
  36. }
  37.  
  38. int go(int v, char ch);
  39.  
  40. int get_link(int v) {
  41. if (trie[v].link == -1) {
  42. if (v == 0 || trie[v].p == 0)
  43. trie[v].link = 0;
  44. else
  45. trie[v].link = go(get_link(trie[v].p), trie[v].pch);
  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. int getleaf(int i) {
  62. if (trie[i].leaflink != -1) {
  63. return trie[i].leaflink;
  64. }
  65. int nxt = get_link(i);
  66. if (nxt > 0) {
  67. if (trie[nxt].leaf != -1) {
  68. trie[i].leaflink = nxt;
  69. } else {
  70. trie[i].leaflink = getleaf(nxt);
  71. }
  72. return trie[i].leaflink;
  73. }
  74. return 0;
  75. }
  76.  
  77. string S;
  78. int N;
  79. int K[MAXN];
  80. string M[MAXN];
  81. vector<int> results[MAXN];
  82.  
  83. int main() {
  84. ios::sync_with_stdio(0);
  85. cin.tie(0);
  86. cin >> S;
  87. cin >> N;
  88. for (int i = 0; i < N; i++) {
  89. cin >> K[i];
  90. cin >> M[i];
  91. add_string(M[i], i);
  92. }
  93.  
  94. int v = 0;
  95. for (int i = 0; i < S.size(); i++) {
  96. v = go(v, S[i]);
  97. int cur = v;
  98. while (getleaf(cur) > 0) {
  99. cur = getleaf(cur);
  100. results[trie[cur].leaf].push_back(i);
  101. }
  102. if (trie[v].leaf != -1) {
  103. results[trie[v].leaf].push_back(i);
  104. }
  105. }
  106. for (int i = 0; i < N; i++) {
  107. int minLength = 1 << 30;
  108. for (int j = K[i]; j <= results[i].size(); j++) {
  109. minLength = min(minLength, results[i][j - 1] - results[i][j - K[i]]);
  110. }
  111. if (minLength == 1 << 30) {
  112. cout << -1 << endl;
  113. } else {
  114. cout << minLength + M[i].size() << endl;
  115. }
  116. }
  117. }
Success #stdin #stdout 0s 8588KB
stdin
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
stdout
3
4
4
-1
5