fork download
copy 
  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
comments (?)
stdin
copy 
aaaaa
5
3 a
3 aa
2 aaa
3 aaaa
1 aaaaa
stdout
copy 
3
4
4
-1
5
https://ideone.com/pE42ue
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!