fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template<typename X, typename Y>
  5. bool chmax(X& a, Y b) { return (a < b) ? a = b, 1 : 0; }
  6.  
  7. template<typename X, typename Y>
  8. bool chmin(X& a, Y b) { return (a > b) ? a = b, 1 : 0; }
  9.  
  10. using ll = long long;
  11.  
  12. const int N = 1e5+5;
  13.  
  14. int k;
  15. string s;
  16.  
  17. struct State {
  18.     int next[26], link, len;
  19.     State() {
  20.         memset(next, 0, sizeof(next));
  21.     }
  22. } sam[2 * N];
  23.  
  24. int sz, last;
  25. int cnt[2 * N], pos[2 * N];
  26.  
  27. void init() {
  28.     sam[0].len = 0;
  29.     sam[0].link = -1;
  30.     sz = 1; last = 0;
  31. }
  32.  
  33. void extend(char ch, int idx) {
  34.     int c = ch - 'a';
  35.     int u = sz++;
  36.     sam[u].len = sam[last].len + 1;
  37.     cnt[u] = 1; pos[u] = idx;
  38.     int p = last;
  39.     while (p != -1 && !sam[p].next[c]) {
  40.         sam[p].next[c] = u;
  41.         p = sam[p].link;
  42.     }
  43.     if (p == -1) sam[u].link = 0;
  44.     else {
  45.         int q = sam[p].next[c];
  46.         if (sam[p].len + 1 == sam[q].len) sam[u].link = q;
  47.         else {
  48.             int v = sz++;
  49.             sam[v].len = sam[p].len + 1;
  50.             sam[v].link = sam[q].link;
  51.             memcpy(sam[v].next, sam[q].next, sizeof(sam[q].next));
  52.             cnt[v] = 0;
  53.             pos[v] = pos[q];
  54.             while (p != -1 && sam[p].next[c] == q) {
  55.                 sam[p].next[c] = v;
  56.                 p = sam[p].link;
  57.             }
  58.             sam[q].link = sam[u].link = v;
  59.         }
  60.     }
  61.     last = u;
  62. }
  63.  
  64. void push_up() {
  65.     vector<int> order(sz, 0);
  66.     for (int i = 0; i < sz; i++) order[i] = i;
  67.     sort(order.begin(), order.end(), [](int x, int y) {
  68.         return sam[x].len > sam[y].len;
  69.     });
  70.     for (int u : order) {
  71.         int p = sam[u].link;
  72.         if (p != -1) {
  73.             cnt[p] += cnt[u];
  74.             chmin(pos[p], pos[u]);
  75.         }
  76.     }
  77. }
  78.  
  79. int query_cnt(string s) {
  80.     int u = 0;
  81.     for (char ch : s) {
  82.         int c = ch - 'a';
  83.         if (!sam[u].next[c]) return 0;
  84.         u = sam[u].next[c];
  85.     }
  86.     return cnt[u];
  87. }
  88.  
  89. int query_pos(string s) {
  90.     int u = 0;
  91.     for (char ch : s) {
  92.         int c = ch - 'a';
  93.         if (!sam[u].next[c]) return -1;
  94.         u = sam[u].next[c];
  95.     }
  96.     return pos[u];
  97. }
  98.  
  99. void solve() {
  100.     cin >> s;
  101.     int n = s.size();
  102.     s = " " + s;
  103.     init();
  104.     for (int i = 1; i <= n; i++) extend(s[i], i);
  105.     push_up();
  106.     cin >> k;
  107.     for (int i = 0; i < k; i++) {
  108.         string p; cin >> p;
  109.         int pos = query_pos(p);
  110.         cout << query_cnt(p) << ' ' << (pos == -1 ? pos : pos - (int)p.size() + 1) << '\n';
  111.     }
  112. }
  113.  
  114. int main() {
  115.     ios_base::sync_with_stdio(false); cin.tie(NULL);
  116.  
  117.     int tests = 1; // cin >> tests;
  118.     while (tests--) solve();
  119.  
  120.     #ifdef LOCAL
  121.     cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  122.     #endif
  123.     return 0;
  124. }
Success #stdin #stdout 0.01s 26136KB
comments (?)
stdin
copy 
aybabtu
3
bab
abc
a
stdout
copy 
1 3
0 -1
2 1
https://ideone.com/23gr1l
language:
C++14 (gcc 8.3)
created:
3 days 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!