题意：对于每个位置，统计有多少个相同的字串。

分析：按照题目的意思,把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*************************************************/#include <bits/stdc++.h>using 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<n;++i)    {        slt.extend(s[i]-‘a‘, i);    }//    for(int i=0;i<n;++i) cout<<ans[i]<<" "; cout<<endl;    for(int i=2;i<n;++i) ans[i] = (2*ans[i-1]-ans[i-2]+ans[i]+MOD)%MOD;    for(int i=0;i<n;++i) printf("%lld\n", ans[i]);        return 0;}

51nod 1600 Simplr KMP(后缀自动机+维护树上的数据结构）