fork download
copy 
  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
comments (?)
stdin
copy 
ABAB
A--CC
stdout
copy 
3
5
3
1
1
2
https://ideone.com/kdUKAQ
language:
C++14 (gcc 8.3)
created:
2 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!