Изменения

string s; int n;

struct node { int l, r, par, link; map<char,int> next;

int len() { return r - l; } int &get (char c) { if (!next.count(c)) next[c] = -1; return next[c]; } }; node t[MAXN]; int sz;

struct state { int v, pos;

}; state ptr (0, 0);

state go (state st, int l, int r) { while (l < r) if (st.pos == t[st.v].len()) {

if (st.v == -1) return st; } else { if (s[ t[st.v].l + st.pos ] != s[l]) return state (-1, -1); if (r-l < t[st.v].len() - st.pos) return state (st.v, st.pos + r-l); l += t[st.v].len() - st.pos; st.pos = t[st.v].len(); } return st; }

int split (state st) { if (st.pos == t[st.v].len()) return st.v; if (st.pos == 0) return t[st.v].par; node v = t[st.v]; int id = sz++; t[id] = node (v.l, v.l+st.pos, v.par); t[v.par].get( s[v.l] ) = id; t[id].get( s[v.l+st.pos] ) = st.v; t[st.v].par = id; t[st.v].l += st.pos; return id; } int get_link (int v) if t[v].link != -1 return t[v].link if t[v].par == -1 return 0 int to = get_link (t[v].par) return t[v].link = split (go (state(to,t[to].len()), t[v].l + (t[v].par==0), t[v].r))

int get_link void tree_extend (int vpos) { if for(t[v].link !;;) state nptr = -go (ptr, pos, pos+1) return t[v].link; if (t[nptr.v].par =!= -1) ptr = nptr return 0; int to mid = get_link split (t[v].parptr); return int leaf = sz++ t[vleaf].link = split node (go (state(topos, n,mid) t[tomid].lenget()), ts[vpos]) = leaf ptr.l + v = get_link (t[v]mid) ptr.parpos ==0), t[ptr.v].rlen()); } if !mid break

void tree_extend (int pos) { for(;;) { state nptr = go (ptr, pos, pos+1); if (nptr.v != -1) { ptr = nptr; return; } int mid = split (ptr); int leaf = sz++; t[leaf] = node (pos, n, mid); t[mid].get( s[pos] ) = leaf; ptr.v = get_link (mid); ptr.pos = t[ptr.v].len(); if (!mid) break; } } void build_tree() { sz = 1;

tree_extend (i); }