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];
  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
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/YIbEn5
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!