peltorator

!Суффиксное Дерево

Jun 14th, 2017
166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef double ld;
  6.  
  7. #define fastRead cin.sync_with_stdio(0); cin.tie(0); cout.tie(0)
  8. #define in(s) freopen(s, "r", stdin);
  9. #define out(s) freopen(s, "w", stdout);
  10. #define fi first
  11. #define se second
  12.  
  13. const int INF = 1e9;
  14. const int MAXN = 2e5 + 239;
  15.  
  16. vector<char> s;
  17. map<int, int> go[MAXN];
  18.  
  19. int len[MAXN], poses[MAXN], suflink[MAXN];
  20. int root = 0, pos = 0;
  21. int _size = 1, n = 0;
  22.  
  23. void goDown()
  24. {
  25.     while(pos > len[go[root][s[n - pos]]])
  26.     {
  27.         root = go[root][s[n - pos]];
  28.         pos -= len[root];
  29.     }
  30. }
  31.  
  32. int f(int curPos, int curLen)
  33. {
  34.     poses[_size] = curPos;
  35.     len[_size] = curLen;
  36.     return _size++;
  37. }
  38.  
  39. void iter(int c)
  40. {
  41.     n++;
  42.     pos++;
  43.     int last = 0;
  44.     while(pos > 0)
  45.     {
  46.         goDown();
  47.         int edge = s[n - pos];
  48.         int &v = go[root][edge];
  49.         int t = s[poses[v] + pos - 1];
  50.         if(v == 0)
  51.         {
  52.             v = f(n - pos, INF);
  53.             suflink[last] = root;
  54.             last = 0;
  55.         }
  56.         else if(t == c)
  57.         {
  58.             suflink[last] = root;
  59.             return;
  60.         }
  61.         else
  62.         {
  63.             int u = f(poses[v], pos - 1);
  64.             go[u][c] = f(n - 1, INF);
  65.             go[u][t] = v;
  66.             poses[v] += pos - 1;
  67.             len [v] -= pos - 1;
  68.             v = u;
  69.             suflink[last] = u;
  70.             last = u;
  71.         }
  72.         if(root == 0)
  73.             pos--;
  74.         else
  75.             root = suflink[root];
  76.     }
  77. }
  78.  
  79. int main()
  80. {
  81.    // in("count.in");
  82.    // out("count.out");
  83.     len[0] = INF;
  84.     string s;
  85.     cin >> s;
  86.     for (int i = 0; i < s.size(); i++)
  87.         iter(S[i]);
  88.     return 0;
  89. }
RAW Paste Data