fork download
  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
stdin
ABAB
A--CC
stdout
3
5
3
1
1
2