给定一个仅包含小写英文字母的字符串，求该字符串含有的本质不同的子串数量。

注：这道题是 SPOJ-694 的加强版

#include<bits/stdc++.h>
using namespace std;
//SAM 统计本质不同的子串个数 
int fail[100050],len[100050];
//fail 指 失配指针 后缀相同endpos不同的最长长度 
//len 指 当前节点的最长串的长度 
int sam[100050][128];
//边 
int pos,tot;// 当前指针pos 和总点数 
long long ans;
char s[500500];
void insert(int x)//插入 
{
    int cur=++tot;//新建节点 
    //cur 对应的状态是 s+x  
    len[cur]=len[pos]+1;//pos 的最长串是插入 x 之前的原串 
    while(pos!=-1&&!sam[pos][x])
    {
        // 这里遍历到的点一定是 pos 的后缀  
        sam[pos][x]=cur;//从没有这个 x 转移的点连边 
        pos=fail[pos];//遍历 
    }
    if(pos==-1)
        fail[cur]=0;
        //如果pos == -1 证明了 这个 x 没有出现过
        //并且连接了所有得边 
    else
    {
        //x出现过 x作为原串 s 的某个后缀t  t+x 的形式出现 
        int temp=sam[pos][x];
        //pos 是 t 所在节点
        //temp 是 t+x 所在节点 这里的temp满足fail 指针的性质 
        //cur 的状态是 s+x 
        if(len[pos]+1==len[temp])//如果pos -> temp 的转移是连续的
        //把cur 接在 temp 的后面 也能遍历到 cur 的所有后缀  
        {
            fail[cur]=temp;
        }
        //实际上我们需要一个这样的节点 fail[cur] 这个点 的最长后缀就是 t+x
        // len[pos]+1==len[temp] 这个temp 就是 最长的后缀一定有 
        else
        {
            //否则需要新建一个这样节点 
            ++tot;//tot的状态是 t 满足性质 fail[cur]=tot 使得tot的状态是 t+x
            len[tot]=len[pos]+1;
            // 这里的tot需要满足line 39 提到的性质 
            // 是将temp 分裂开 temp 对应的状态是 t+x
            // pos 的状态是 t 
            for(int i=0;i<128;i++)
            {
                sam[tot][i]=sam[temp][i];
            }
            fail[tot]=fail[temp];//先复制temp 
            while(pos!=-1&&sam[pos][x]==temp)//temp 的前缀都连着 x 这个边 
            {
                //将指向temp的x边都指向tot
                //因为不连续 那么 一定有其他路径可以到达这个temp点 所以最长的也就是len 不会改变 
                sam[pos][x]=tot; 
                pos=fail[pos];//pos的后缀也要改 
            }
            fail[temp]=fail[cur]=tot;//tot 既是temp的后缀 也是 temp的后缀 
        }
    }
    pos=cur;//更新pos 
    ans+=len[cur]-len[fail[cur]];//统计答案  
}
int main()
{
    int T;
    scanf("%d",&T);//多组数据 
    while(T--)
    {
        memset(fail,0,sizeof fail);
        memset(len,0,sizeof len);
        memset(sam,0,sizeof sam);
        ans=tot=pos=0;//init
        fail[0]=-1;//init
        scanf("%s",s+1);
        int lens=strlen(s+1);
        for(int i=1;i<=lens;i++)
        {
            insert(s[i]);//输入 并逐位插入 这也反应了SAM是一个在线算法 
        }
        printf("%lld\n",ans);//答案 
    }
    return 0;
}