peltorator

!Суффиксный Автомат

Jun 14th, 2017
210
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 MAXN = 2.3e6, ALF = 26;
  14.  
  15. int g[MAXN][ALF], suf[MAXN], len[MAXN], last, n;
  16.  
  17. void iter(int c)
  18. {
  19.     int newLast = n;
  20.     n++;
  21.     int p = last;
  22.     len[newLast] = len[p] + 1;
  23.     while (p != -1 && g[p][c] == -1)
  24.     {
  25.         g[p][c] = newLast;
  26.         p = suf[p];
  27.     }
  28.     if (p == -1)
  29.         suf[newLast] = 0;
  30.     else
  31.     {
  32.         int q = g[p][c];
  33.         if (len[q] == len[p] + 1)
  34.             suf[newLast] = q;
  35.         else
  36.         {
  37.             int r = n;
  38.             n++;
  39.             for (int i = 0; i < ALF; i++)
  40.                 g[r][i] = g[q][i];
  41.             suf[r] = suf[q];
  42.             len[r] = len[p] + 1;
  43.             while (p != -1 && g[p][c] == q)
  44.             {
  45.                 g[p][c] = r;
  46.                 p = suf[p];
  47.             }
  48.             suf[q] = suf[newLast] = r;
  49.         }
  50.     }
  51.     last = newLast;
  52. }
  53.  
  54. vector<int> term;
  55.  
  56. int main()
  57. {
  58.    // in("count.in");
  59.    // out("count.out");
  60.     for (int i = 0; i < MAXN; i++)
  61.     {
  62.         suf[i] = -1;
  63.         for (int j = 0; j < ALF; j++)
  64.             g[i][j] = -1;
  65.     }
  66.     n = 1;
  67.     last = 0;
  68.     len[0] = 0;
  69.     suf[0] = -1;
  70.     string s;
  71.     cin >> s;
  72.     for (int i = 0; i < s.size(); i++)
  73.         iter(s[i] - 'a');
  74.     return 0;
  75. }
RAW Paste Data