fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define endl "\n"
  4.  
  5. struct suffixAutomaton {
  6.     struct node {
  7.         int len, link, cnt;
  8.         int next[26];
  9.     };
  10.  
  11.     vector<node> sa;
  12.     vector<int> last, p1, p2, q1, qlink;
  13.     long long ans = 0;
  14.     string s;
  15.  
  16.     suffixAutomaton(int mx_len) {
  17.         sa.reserve(mx_len*2);
  18.         last.push_back(add_node());
  19.         sa[0].link = -1;
  20.     }
  21.  
  22.     int add_node() { sa.push_back(node()); return sa.size()-1; }
  23.  
  24.     void add_char(char ch) {
  25.         s.push_back(ch);
  26.         int c = ch-'A';
  27.         int u = add_node(), p = last.back();
  28.         sa[u].len = sa[p].len + 1;
  29.         while (p != -1 && !sa[p].next[c]) {
  30.             sa[p].next[c] = u;
  31.             p = sa[p].link;
  32.         }
  33.         p1.push_back(p);
  34.         if (p != -1) {
  35.             int q = sa[p].next[c];
  36.             q1.push_back(q);
  37.             if (sa[p].len + 1 != sa[q].len) {
  38.                 int clone = add_node();
  39.                 sa[clone] = sa[q];
  40.                 sa[clone].len = sa[p].len + 1;
  41.                 qlink.push_back(sa[q].link);
  42.                 sa[q].link = sa[u].link = clone;
  43.                 while (p != -1 && sa[p].next[c] == q) {
  44.                     sa[p].next[c] = clone;
  45.                     p = sa[p].link;
  46.                 }
  47.                 p2.push_back(p);
  48.             } else sa[u].link = q;
  49.             int v = sa[u].link;
  50.             if (!sa[v].cnt) ans += sa[v].len - sa[sa[v].link].len;
  51.             sa[v].cnt++;
  52.         }
  53.         last.push_back(u);
  54.     }
  55.  
  56.     void pop_back() {
  57.         int c = s.back()-'A'; s.pop_back();
  58.         int u = last.back(); last.pop_back();
  59.         int p = last.back();
  60.         while (p != p1.back()) {
  61.             sa[p].next[c] = 0;
  62.             p = sa[p].link;
  63.         }
  64.         p1.pop_back();
  65.         if (p != -1) {
  66.             int v = sa[u].link;
  67.             sa[v].cnt--;
  68.             if (!sa[v].cnt) ans -= sa[v].len - sa[sa[v].link].len;
  69.             int q = q1.back(); q1.pop_back();
  70.             if (sa[p].len + 1 != sa[q].len) {
  71.                 sa[q].link = qlink.back(); qlink.pop_back();
  72.                 while (p != p2.back()) {
  73.                     sa[p].next[c] = q;
  74.                     p = sa[p].link;
  75.                 }
  76.                 p2.pop_back();
  77.                 sa.pop_back();
  78.             }
  79.         }
  80.         sa.pop_back();
  81.     }
  82.  
  83.     node& operator[](int i) { return sa[i]; }
  84. };
  85.  
  86. int main() {
  87.     ios::sync_with_stdio(0);
  88.     cin.tie(0);
  89.  
  90.     string s, q;
  91.     cin >> s >> q;
  92.     int len = s.size() + q.size();
  93.  
  94.     suffixAutomaton sa(len);
  95.  
  96.     for (auto &c : s) sa.add_char(c);
  97.     cout << sa.ans << endl;
  98.  
  99.     for (auto &c : q) {
  100.         if (c == '-') sa.pop_back();
  101.         else sa.add_char(c);
  102.         cout << sa.ans << endl;
  103.     }
  104. }
Success #stdin #stdout 0.01s 5436KB
comments (?)
stdin
copy 
ABAB
A--CC
stdout
copy 
3
5
3
1
1
2
https://ideone.com/v7mFBa
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!