fork(1) download
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <iostream>
  4. #include <vector>
  5. #include <numeric>
  6. #include <set>
  7.  
  8. using namespace std;
  9. #define endl '\n'
  10.  
  11. struct SuffixArrayTree
  12. {
  13.  
  14. SuffixArrayTree() : root(-1), up(1), sa(1)
  15. {
  16. root = new_node(-1, -1);
  17. }
  18.  
  19. void push(int c)
  20. {
  21. int old_root = root;
  22. root = new_node(c, root);
  23. if (old_root != -1)
  24. children[old_root].push_back(root);
  25. queries.push_back(root);
  26. }
  27.  
  28. void pop()
  29. {
  30. assert(root != -1);
  31. root = up[0][root];
  32. queries.push_back(root);
  33. }
  34.  
  35. void record()
  36. {
  37. queries.clear();
  38. queries.push_back(root);
  39. }
  40.  
  41. int compare(int u, int v, vector<int> &up, vector<int> &sa, vector<int> &len)
  42. {
  43. if (sa[u] != sa[v])
  44. return sa[u] < sa[v] ? +1 : -1;
  45. if (up[u] == -1 || up[v] == -1)
  46. {
  47. if (len[u] == len[v])
  48. return 0;
  49. return len[u] < len[v] ? +1 : -1;
  50. }
  51. u = up[u], v = up[v];
  52. if (sa[u] == sa[v])
  53. return 0;
  54. return sa[u] < sa[v] ? +1 : -1;
  55. }
  56.  
  57. void build()
  58. {
  59. int n = sa[0].size();
  60.  
  61. // compute len of each string
  62. for (int i = 0; i < n; ++i)
  63. {
  64. if (up[0][i] == -1)
  65. len[i] = 0;
  66. else
  67. len[i] = len[up[0][i]] + 1;
  68. }
  69.  
  70. // Build suffix array
  71. for (int i = 0; i < 20; ++i)
  72. {
  73. vector<int> u(n), s(n); // up row + suffix array row
  74.  
  75. auto &ub = up.back();
  76. auto &sb = sa.back();
  77.  
  78. for (int i = 0; i < n; ++i)
  79. u[i] = ub[i] == -1 ? -1 : ub[ub[i]];
  80.  
  81. iota(s.begin(), s.end(), 0);
  82. sort(s.begin(), s.end(), [&](int &u, int &v)
  83. { return compare(u, v, ub, sb, len) == +1; });
  84.  
  85. vector<int> row(n);
  86. for (int i = 1; i < n; ++i)
  87. {
  88. int u = s[i - 1], v = s[i];
  89. int c = compare(u, v, ub, sb, len);
  90. assert(c >= 0);
  91. row[v] = row[u] + c;
  92. }
  93.  
  94. order = s;
  95. up.push_back(u);
  96. sa.push_back(row);
  97. }
  98.  
  99. rank = vector<int>(n);
  100. for (int i = 0; i < n; ++i)
  101. rank[order[i]] = i;
  102.  
  103. // Build lcp
  104. lcp = vector<int>(n - 1);
  105. for (int i = 0; i + 1 < n; ++i)
  106. lcp[i] = find_lcp_log(order[i], order[i + 1]);
  107.  
  108. // Build rmq table for lcp
  109. rmq.push_back(lcp);
  110. for (int i = 1; (1 << i) <= n - 1; ++i)
  111. {
  112. vector<int> r(n - 1);
  113. for (int j = 0; j + (1 << i) <= n - 1; ++j)
  114. r[j] = min(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
  115. rmq.push_back(r);
  116. }
  117.  
  118. log2 = vector<int>(n + 1);
  119. for (int i = 2; i <= n; ++i)
  120. log2[i] = 1 + log2[i / 2];
  121.  
  122. set<int> s;
  123. dfs(0, s);
  124. }
  125.  
  126. void print()
  127. {
  128. for (auto u : queries)
  129. cout << answer[u] << '\n';
  130. }
  131.  
  132. private:
  133. int root;
  134. vector<int> order, rank, lcp, log2, len, queries;
  135. vector<long long> answer;
  136. vector<vector<int>> up, rmq, sa, children;
  137.  
  138. int new_node(int value, int parent)
  139. {
  140. sa.back().push_back(value);
  141. up.back().push_back(parent);
  142. len.push_back(0);
  143. answer.push_back(0);
  144. children.push_back({});
  145. return sa.back().size() - 1;
  146. }
  147.  
  148. int find_lcp_log(int u, int v)
  149. {
  150. int answer = 0;
  151.  
  152. for (int l = sa.size() - 1; u != -1 && v != -1 && l >= 0; --l)
  153. {
  154. if ((1 << l) <= len[u] && sa[l][u] == sa[l][v])
  155. {
  156. answer += 1 << l;
  157. u = up[l][u];
  158. v = up[l][v];
  159. }
  160. }
  161.  
  162. return answer;
  163. }
  164.  
  165. int find_lcp_from_rank(int pu, int pv)
  166. {
  167. // int pu = rank[u];
  168. // int pv = rank[v];
  169. if (pu > pv)
  170. swap(pu, pv);
  171. pv--;
  172. int sz = pv - pu + 1;
  173. int lg = log2[sz];
  174. return min(rmq[lg][pu], rmq[lg][pv - (1 << lg) + 1]);
  175. }
  176.  
  177. void dfs(int u, set<int> &s)
  178. {
  179. // Try insert
  180. int r = rank[u];
  181. auto it = s.lower_bound(r);
  182.  
  183. // [l2] ... [l1] ... [r] ... [r1] ... [r2]
  184. int l2 = 0, l1 = 0, r1 = 0, r2 = 0, c = 0;
  185.  
  186. if (it != s.end())
  187. {
  188. if (it != s.begin())
  189. {
  190. int b = *--it;
  191. int a = *++it;
  192. c = find_lcp_from_rank(a, b);
  193. }
  194.  
  195. r1 = find_lcp_from_rank(r, *it);
  196. if (++it != s.end())
  197. r2 = find_lcp_from_rank(r, *it);
  198. --it;
  199. }
  200.  
  201. if (it != s.begin())
  202. {
  203. l1 = find_lcp_from_rank(*--it, r);
  204. if (it != s.begin())
  205. l2 = find_lcp_from_rank(*--it, r);
  206. }
  207.  
  208. int new_delta = max(l1, r1) - max({l2, r2, c});
  209.  
  210. answer[u] += new_delta;
  211.  
  212. s.insert(r);
  213.  
  214. for (auto v : children[u])
  215. {
  216. answer[v] = answer[u];
  217. dfs(v, s);
  218. }
  219.  
  220. s.erase(r);
  221. }
  222. };
  223.  
  224. int main()
  225. {
  226. ios_base::sync_with_stdio(0);
  227. cin.tie(0);
  228.  
  229. string s, q;
  230. cin >> s >> q;
  231.  
  232. SuffixArrayTree tree;
  233.  
  234. for (auto c : s)
  235. tree.push(c - 'A');
  236.  
  237. tree.record();
  238.  
  239. for (auto c : q)
  240. {
  241. if (c == '-')
  242. tree.pop();
  243. else
  244. tree.push(c - 'A');
  245. }
  246.  
  247. tree.build();
  248. tree.print();
  249. }
  250.  
Success #stdin #stdout 0s 5520KB
stdin
ABAB
A--CC
stdout
3
5
3
1
1
2