Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.11 KB | None | 0 0
  1. const int MAXLEN = 600000;
  2. string s;
  3. int pos[MAXLEN], len[MAXLEN], par[MAXLEN];
  4. map<char,int> to[MAXLEN], link[MAXLEN];
  5. int sz = 2;
  6. int path[MAXLEN];
  7. void attach(int child, int parent, char c, int child_len)
  8. {
  9.     to[parent][c] = child;
  10.     len[child] = child_len;
  11.     par[child] = parent;
  12. }
  13. void extend(int i)
  14. {
  15.     int v, vlen = s.size() - i, old = sz - 1, pstk = 0;
  16.     for (v = old; !link[v].count(s[i]); v = par[v]) {
  17.         vlen -= len[v];
  18.         path[pstk++] = v;
  19.     }
  20.     int w = link[v][s[i]];
  21.     if (to[w].count(s[i + vlen])) {
  22.         int u = to[w][s[i + vlen]];
  23.         for (pos[sz] = pos[u] - len[u]; s[pos[sz]] == s[i + vlen]; pos[sz] += len[v]) {
  24.             v = path[--pstk];
  25.             vlen += len[v];
  26.         }
  27.         attach(sz, w, s[pos[u] - len[u]], len[u] - (pos[u] - pos[sz]));
  28.         attach(u, sz, s[pos[sz]], pos[u] - pos[sz]);
  29.         w = link[v][s[i]] = sz++;
  30.     }
  31.     link[old][s[i]] = sz;
  32.     attach(sz, w, s[i + vlen], s.size() - (i + vlen));
  33.     pos[sz++] = s.size();
  34. }
  35. int main()
  36. {
  37.     len[1] = 1; pos[1] = 0; par[1] = 0;
  38.     for (int c = 0; c < 256; c++)
  39.         link[0][c] = 1;
  40.     s = "abababasdsdfasdf";
  41.     for (int i = s.size() - 1; i >= 0; i--)
  42.         extend(i);
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement