题意：对于每个位置，统计有多少个相同的字串。
分析：按照题目的意思,把fail树画出来就会发现，对于第i个字符：ans[i] = ans[i-1] + (ans[i-1]-ans[i-1]) + cal(i);
cal(i)是计算s[1…i-1]所有子串与s[1…i]的最长公共后缀的和。换句话说，根据后缀自动机性质，沿着parent树往上走可以知道对于后缀s[1…i]的所有位置的公共后缀长度以及个数（right集合的大小）。很容易可以计算出cal(i), 只要每次新增一个字符的时候，在parent树上往根走，边走边统计 val[i]*(right[pre[i]]-right[i])。由于博主我是在建后缀自动机的同时计算ans，所以parent树是动态地边的，所以博主用了LCT去维护。
吐槽：看问题的角度果然可以有好多，显然下面代码能折射出我看问题的角度显然不太好。为了这道题，苦苦地学了LCT，然而后来看别人博客发现可以直接用树链剖分写的。
/************************************************Author :DarkTongCreated Time :2016/9/6 22:58:31File Name :51nod_simpleKMP.cpp*************************************************/#includeusing namespace std;typedef unsigned long long ULL;typedef long long LL;const int INF = 0x3f3f3f3f;const double eps = 1e-9;const int MOD = 1e9+7;const int maxn = 2*100000 + 100;LL ans[maxn];struct Splay_Tree{ int ch[maxn][2], pre[maxn], dpre[maxn]; // dpre用于树-树连接 // pre用于树内连接 int lazy[maxn], mval[maxn], mr[maxn]; LL sum[maxn]; int go[maxn][26], right[maxn], val[maxn]; int sz, last, root; void pushdown(int x){ int l = ch[x][0], r = ch[x][1]; if(l)lazy[l] += lazy[x], right[l] += lazy[x], mr[l] += lazy[x]; if(r)lazy[r] += lazy[x], right[r] += lazy[x], mr[r] += lazy[x]; lazy[x] = 0; mr[x] = max(right[x], max(mr[l], mr[r])); } void pushup(int x){ sum[x] = (sum[ch[x][0]] + sum[ch[x][1]] + val[x]*mval[x])%MOD; mr[x] = max(right[x], max(mr[ch[x][0]], mr[ch[x][1]])); //ch[x][1] 不是 x的儿子，因为x不是根。 } //旋转操作(ok)，请注意：对于被旋转的元素，其dpre=0，也就是说是对辅助树在操作，不影响到原树。 void rotate(int x){ int y = pre[x], d = (ch[y][1]==x); ch[y][d] = ch[x][!d]; pre[ch[x][!d]] = y; pre[x] = pre[y]; pre[y] = x; ch[x][!d] = y; if(dpre[y]) dpre[y]=0, dpre[x]=1; else ch[pre[x]][ch[pre[x]][1]==y] = x; pushup(y);// pushup(x); } //直接访问节点o,并将其选转至根部 void P(int x){ if(!dpre[x]) P(pre[x]); //找重链的根，然后把标志向下传一遍 pushdown(x); } void splay(int x){ P(x); while(!dpre[x]){ int f = pre[x], ff = pre[f]; if(dpre[f]) rotate(x); else if( (ch[ff][1]==f) == (ch[f][1]==x) ) rotate(f), rotate(x); else rotate(x), rotate(x); } pushup(x); } //AuxiliaryTree链接操作(数据更新) void Access(int x){ int y = 0; for(;x;y=x, x=pre[x]){ splay(x); //为了去掉元重儿子，旋转后儿子在其左子树 dpre[ch[x][1]] = 1; //去掉元重儿子 ch[x][1] = y; dpre[y] = 0; //加入新的重儿子v mval[x] = right[x] - mr[ch[x][1]]; pushup(x); } } //加边，连接两棵树，u->v; void link(int u, int v) { Access(u); pre[u]=v; dpre[u] = 1; Access(u); } void cut(int x) { Access(x); splay(x); int l = ch[x][0]; pre[l] = 0; dpre[l] = 1; ch[x][0] = 0; Access(x); } int fa(int u){ Access(u); splay(u); u = ch[u][0]; while(ch[u][1]) u = ch[u][1]; return u; } void SAM(){ last = root = sz = 1; } void ini(int sz, int v){ val[sz] = v;mval[sz] = 0; ch[sz][0]=ch[sz][1]=0; dpre[sz] = 1; pre[sz]=sum[sz]=lazy[sz]=right[sz]=0; mr[sz]=0; memset(go[sz], 0, sizeof go[sz]); } void extend(int w, int th) { int p = last; int np = ++sz; ini(sz, val[p]+1); //叶子节点 while(p && go[p][w] == 0) go[p][w] = np, p = fa(p); if(p == 0) link(np, root); else{ int q = go[p][w]; if(val[p] + 1 == val[q]) link(np, q); else{ int nq = ++sz; ini(sz, val[p]+1); //非叶子节点 memcpy(go[nq], go[q], sizeof go[q]); mr[nq] = right[nq] = right[q]; mval[nq] = right[q]; int faq = fa(q); cut(q); link(q, nq); link(np, nq); link(nq, faq); while(p && go[p][w] == q) go[p][w] = nq, p = fa(p); } } last = np; ans[th] = cal(np); } LL cal(int x) { x = fa(x); Access(x); splay(x); //update lazy[x]++; right[x]++; mval[x] = right[x]; pushup(x); return sum[x]; }}slt;char s[maxn];int main(){// freopen("out.txt", "r", stdin);// freopen("xx1.txt", "w", stdout); int T, cas=1, n; scanf("%d%s", &n, s); slt.SAM(); slt.ini(1, 0); for(int i=0;i