1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int seq[2*maxn],indeg[2*maxn],tot,slink[2*maxn],trans[2*maxn][26],maxlen[2*maxn];
bool isy[2*maxn];
int newstate(int _maxlen,int *_trans,int _slink)
{
    slink[++tot]=_slink;
    maxlen[tot]=_maxlen;
    if(_trans)
        for(int i=0;i<26;i++)
        {
            trans[tot][i]=_trans[i];
            indeg[_trans[i]]++;
        }
    return tot;
}
int addchar(char ch,int u)
{
    int c=ch-'a',v=u,z=newstate(maxlen[v]+1,NULL,0);
    while(v&&!trans[v][c])
    {
        trans[v][c]=z;
        indeg[z]++;
        v=slink[v];
    }
    if(!v)
    {
        slink[z]=1;
        return z;
    }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX