回文树&后缀自动机&后缀数组

• KMP，扩展KMP和Manacher就不写了，感觉没多大意思。
   
• 之前感觉后缀自动机简直可以解决一切，所以不怎么写后缀数组。
   
• 马拉车主要是通过对称中心解决问题，有的时候要通过回文串的边界解决问题，这个时候回文树就用到了，又好写，又强大。
   
• 之前整理过一篇后缀自动机的。感觉还要整理一下，顺便把回文树，后缀数组也整理一下

• 很久没写专题了，如果有空，把回文自动机也学习一下。

一：回文树

前置技能： 马拉车，KMP。 其实也没关系，就是对比一下。

马拉车是利用对称的思想，得到每个点或者空格为对称中心的最长回文。

KMP有失配指针，回文树也有，指向失配后最长的回文串。

前置理论： 一个字符串的本质不同的回文串最多有|S|个。所以，回文树的空间和时间是线性的。

保存信息：我们把每个回文串对应到一个节点里。

     struct node{
           int len,num,fail,son[],dep;
     }t[maxn];

其中，len是回文串的长度；num是出现次数；son是儿子指针，用于匹配，看是否能增加长度；dep是指这个回文串失配次数，即以它的最后一个字符为尾的回文串个数； fail是失配指针；

功能：我们可以得到所有的回文串； 所有本质不同的回文串； 回文串的出现次数； 以某个位置结尾的回文串个数；

实现：首先，初始化两个节点1号和0号，分别表示奇数偶数长度的回文串。 他们都指向1号节点，而1号节点的长度设置尾-1，这样的话，确保每个位置结尾的回文串长度至少是-1+2=1；

    void init()
    {
        tot=last=;
        t[].len=; t[].len=-;
        t[].fail=t[].fail=;
    }

完整代码：

struct PAT
{
    struct node{
        int len,num,fail,son[];
    }t[maxn];
    int last,n,tot,s[maxn];
    void init()
    {
        memset(t,,sizeof(t));
        tot=last=; n=;
        t[].len=; t[].len=-;
        t[].fail=t[].fail=;
        s[]=-;
    }
    int add(int c){
        int p=last; s[++n]=c;
        while(s[n]!=s[n--t[p].len]) p=t[p].fail;
        if(!t[p].son[c]){
            int v=++tot,k=t[p].fail;
            while(s[n]!=s[n-t[k].len-]) k=t[k].fail;
            t[v].fail=t[k].son[c];
            t[v].len=t[p].len+;
            t[v].num=t[t[v].fail].num+;
            t[p].son[c]=v;
        }
        last=t[p].son[c];
        return t[last].num;
    }
}T;

例题一：HDU5658：CA Loves Palindromic

题意：给定字符串S，|S|<1000；Q次询问区间不用本质的回文串数量。

思路：以每个左端点建立回文树即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn]; int bb[maxn];
int N,Q,fcy[maxn][maxn];
struct PT
{
    struct node{
        int fail,len,son[];
    }t[maxn];
    int tot,last;
    void init()
    {
        memset(t,,sizeof(t));
        t[].fail=t[].fail=;
        t[].len=-;
        last=; tot=; bb[]=-; bb[]=-;
    }
    void add(int s,int n)
    {
        int p=last; bb[n]=s;
        while(bb[n-t[p].len-]!=bb[n]) p=t[p].fail;
        if(!t[p].son[s])
        {
            int v=++tot,k=t[p].fail;
            t[v].len=t[p].len+;
            while(bb[n-t[k].len-]!=bb[n]) k=t[k].fail;
            t[v].fail=t[k].son[s];
            t[p].son[s]=v;
        }
        last=t[p].son[s];
    }
}T;
void solve()
{
    rep(i,,N){
        T.init();
        rep(j,i,N) {
            T.add(c[j]-'a',j-i+);
            fcy[i][j]=T.tot-;
        }
    }
    scanf("%d",&Q);
    rep(i,,Q){
       int L,R; scanf("%d%d",&L,&R);
       printf("%d\n",fcy[L][R]);
    }
}
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        memset(c,,sizeof(c));
        scanf("%s",c+);
        N=strlen(c+);
        solve();
    }
    return ;
}

例题二：HDU - 5157 ：Harry and magic string

题意： 多组输入，每次给定字符串S（|S|<1e5），求多少对不相交的回文串。

思路：可以用回文树求出以每个位置结尾的回文串数，那么累加得到前缀和； 倒着再做一遍得到每个位置为开头的回文串数，乘正向求出的前缀和即可。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=;
struct PAT
{
    struct node{
        int len,num,fail,son[];
    }t[maxn];
    int last,n,tot,s[maxn];
    void init()
    {
        memset(t,,sizeof(t));
        tot=last=; n=;
        t[].len=; t[].len=-;
        t[].fail=t[].fail=;
        s[]=-;
    }
    int add(int c){
        int p=last; s[++n]=c;
        while(s[n]!=s[n--t[p].len]) p=t[p].fail;
        if(!t[p].son[c]){
            int v=++tot,k=t[p].fail;
            while(s[n]!=s[n-t[k].len-]) k=t[k].fail;
            t[v].fail=t[k].son[c];
            t[v].len=t[p].len+;
            t[v].num=t[t[v].fail].num+;
            t[p].son[c]=v;
        }
        last=t[p].son[c];
        return t[last].num;
    }
}T;
ll ans,sum[maxn];char c[maxn];
int main()
{
    while(~scanf("%s",c+)){
        int N=strlen(c+);
        T.init(); ans=;
        rep(i,,N) sum[i]=sum[i-]+T.add(c[i]-'a');
        T.init();
        rep2(i,N,) ans+=sum[i-]*T.add(c[i]-'a');
        printf("%lld\n",ans);
    }
    return ;
}

例题三：HDU - 5785：Interesting

题意：累计i*k的和，如果[i,j],[j+1,k]都是回文串;

思路：统计以j为结尾的回文串个数numj，以及他们的长度和addj； 以j+1为首....；那么这个位置的贡献就是(numj*(j+1)-addj)*(numj+1*j+addj+1);

(此题要节约空间，所以不要开longlong的数组。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=;
const int Mod=1e9+;
struct PAT
{
    struct node{
        int len,num,fail,son[],add;
    }t[maxn];
    int last,n,tot,s[maxn];
    void init()
    {
        memset(t,,sizeof(t));
        tot=last=; n=;
        t[].len=; t[].len=-;
        t[].fail=t[].fail=;
        s[]=-;
    }
    void add(int c){
        int p=last; s[++n]=c;
        while(s[n]!=s[n--t[p].len]) p=t[p].fail;
        if(!t[p].son[c]){
            int v=++tot,k=t[p].fail;
            while(s[n]!=s[n-t[k].len-]) k=t[k].fail;
            t[v].fail=t[k].son[c];
            t[v].len=t[p].len+;
            t[v].num=t[t[v].fail].num+;
            t[v].add=(t[t[v].fail].add+t[v].len)%Mod;
            t[p].son[c]=v;
        }
        last=t[p].son[c];
    }
}T;
int ans,sum[maxn];char c[maxn];
int main()
{
    while(~scanf("%s",c+)){
        int N=strlen(c+);
        T.init(); ans=;
        rep(i,,N) {
            T.add(c[i]-'a');
            sum[i]=(1LL*T.t[T.last].num*(i+)-T.t[T.last].add)%Mod;
        }
        T.init();
        rep2(i,N,){
            T.add(c[i]-'a');
            ans+=(ll)(T.t[T.last].add+1LL*T.t[T.last].num*(i-)%Mod)*sum[i-]%Mod;
            ans%=Mod;
        }
        printf("%d\n",ans);
    }
    return ;
}

例题四：HDU - 5421：Victor and String

题意：多组输入，开始字符串为空，支持4中操作： 1，在字符串首加字符； 2，在字符串尾加字符； 3，查询字符串不同本质的回文串个数； 4，查询回文串个数总和

思路：因为支持首尾加入，所以和常规的回文树有些不同。 参考了YYB的博客。 发现首尾互相影响，当且仅当整个字符串是回文串。 其他情况两头正常加即可。

也就是现在有两个last，除了完全对称，其他操作都一样。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define rep2(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int maxn=;
struct PAT
{
    struct node{
        int len,num,fail,son[];
    }t[maxn];
    int n,tot,s[maxn<<],L,R,suf,pre; ll ans;
    void init()
    {
        memset(t,,sizeof(t));
        memset(s,-,sizeof(s));
        tot=; L=; R=L-;
        suf=pre=; ans=;
        t[].len=-; t[].fail=t[].fail=;
    }
    void add(int c,int n,int &last,int op){
        int p=last; s[n]=c;
        while(s[n]!=s[n-op-op*t[p].len]) p=t[p].fail;
        if(!t[p].son[c]){
            int v=++tot,k=t[p].fail;
            while(s[n]!=s[n-op*t[k].len-op]) k=t[k].fail;
            t[v].fail=t[k].son[c];
            t[v].len=t[p].len+;
            t[v].num=t[t[v].fail].num+;
            t[p].son[c]=v;
        }
        last=t[p].son[c]; ans+=t[last].num;
        if(t[last].len==R-L+) suf=pre=last;
    }
}T;
int main()
{
    int N;
    while(~scanf("%d",&N)){
        T.init(); int opt;
        rep(i,,N){
            scanf("%d",&opt); char s[];
            if(opt==){
                scanf("%s",s);
                T.add(s[]-'a',--T.L,T.pre,-);
            }
            else if(opt==){
                scanf("%s",s);
                T.add(s[]-'a',++T.R,T.suf,);
            }
            else if(opt==)
                printf("%d\n",T.tot-);
            else printf("%lld\n",T.ans);
        }
    }
    return ;
}

例题五：Gym - 101981M：（南京） Mediocre String Problem

题意：给字符串S和T，累计（i结尾的回文串个数）*（i+1开始匹配T的长度）。

思路：第一部分用回文树，第二部分exkmp。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char S[maxn],T[maxn];
struct PT
{
    struct in{
        int dep,fail,len,son[];
    }p[maxn];
    int cnt,last;
    void init()
    {
        //memset(p,0,sizeof(p));
        cnt=last=;p[].dep=p[].dep=;
        p[].fail=p[].fail=;
        p[].len=; p[].len=-;
    }
    int add(int c,int n)
    {
        int np=last;
        while(S[n]!=S[n--p[np].len]) np=p[np].fail;
        if(!p[np].son[c]){
            int v=++cnt,k=p[np].fail; p[v].len=p[np].len+;
            while(S[n]!=S[n-p[k].len-]) k=p[k].fail;
            p[v].fail=p[k].son[c];
            p[np].son[c]=v; //这一句放前面会出现矛盾，因为np可能=k
            p[v].dep=p[p[v].fail].dep+;
        }
        last=p[np].son[c];
        return p[last].dep;
    }
}Tree;
int N,M,num[maxn],Next[maxn],extand[maxn]; ll ans;
void getnext(){// next[i]: 以第i位置开始的子串与T的公共前缀长度
     int i,length=strlen(T+);
     Next[]=length;
     for(i=;i+<length&&T[i+]==T[i+];i++);
     Next[]=i;
     int a=;   //!
     for(int k=;k<=length;k++){//长度+1，位置-1。
          int p=a+Next[a]-, L=Next[k-a+];
          if(L>=p-k+){
              int j=(p-k+)>?(p-k+):;//中断后可能是负的
              while(k+j<=length&&T[k+j]==T[j+]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较
              Next[k]=j, a=k;
          }
          else Next[k]=L;
    }
}
void getextand(){
    memset(Next,,sizeof(Next));
    getnext();
    int Slen=strlen(S+),Tlen=strlen(T+),a=;
    int MinLen=Slen>Tlen?Tlen:Slen;
    while(a<MinLen&&S[a+]==T[a+]) a++;
    extand[]=a; a=;
    for(int k=;k<=Slen;k++){
        int p=a+extand[a]-,L=Next[k-a+];
        if(L>=p-k+){
            int j=(p-k+)>?(p-k+):;
            while(k+j<=Slen&&j+<=Tlen&&S[k+j]==T[j+]) j++;
            extand[k]=j;a=k;
        }
        else extand[k]=L;
    }
}
int main()
{
    scanf("%s%s",S+,T+);
    N=strlen(S+); M=strlen(T+);
    reverse(S+,S+N+); Tree.init();
    rep(i,,N) num[i]=Tree.add(S[i]-'a',i);
    getextand();
    rep(i,,N) ans+=(ll)num[i-]*extand[i];
    printf("%lld\n",ans);
    return ;
}

二：后缀自动机

技能前置：由于本质不同的回文串最多|S|个，所以回文树的（时间和）空间是线性的。

后缀自动机也也差不多，不过空间开两倍。 但是并不是代表本质不同的字符串最多2|S|个，因为后缀自动机保存的是集合。

保存信息：回文树保存的是回文串的信息，而后缀自动机保存的是集合的信息。 集合里最长的串长度为maxlen[i]；集合大小为maxlen[i]-maxlen[fa[i]]；

而fa和ch数组的交叉复杂的DAG图，感觉初学有点难以理解的，原理还是自己去看吧。。。

功能：对于单个字符串S。可以求，不同子串个数； 个子串的长度； 最小表示法； etc。

对于多个串。 我们可以求最长公共子串； 以及各种匹配（匹配的长度需要记录，注意和集合最长长度maxlen区分）；etc。

构造：增量法，每次加入一个字符，由于一定会增加一个新串s[1,i]，所以节点数cnt++，sz[cnt]=1，maxlen[cnt]=i；然后往上走，直到有冲突，或者遇到根 。

1，遇到根(root=1)，表示全是可以接纳的，那么fa[np]=1;

2，一开始就遇到冲突的，即maxlen[q]==maxlen[p]+1，那么fa[np]=q即可。

3，中途遇到冲突，由于每个集合保存的信息的一样的，那么需要分叉(新的nq节点继续跑)。

    int add(int x)
    {
       int np=++cnt,p=last; last=np;
       maxlen[np]=maxlen[p]+; sz[np]=;
       while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
       if(!p) fa[np]=;
       else {
         int q=ch[p][x];
         if(maxlen[q]==maxlen[p]+) fa[np]=q;
         else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            fa[nq]=fa[q]; fa[q]=fa[np]=nq;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
         }
       }
    }

topo排序：和SA一样，基数较小，我们可以基数排序。 得到每个集合里的串出现次数。

    void sort()
    {
       rep(i,,cnt) a[i]=;
       rep(i,,cnt) a[maxlen[i]]++;
       rep(i,,cnt) a[i]+=a[i-];
       rep(i,,cnt) b[a[maxlen[i]]--]=i;
       for(int i=cnt;i>=;i--) sz[fa[b[i]]]+=sz[b[i]];
    }

例题一：UVA - 719Glass Beads

题意：给定字符串，求最小表示法的起始位置。 |S|<1e4

思路：我们把字符串加倍，丢到自动机里面。 由于我加倍了，所以去匹配的时候可以保证长度不小于|S|，即从第一位到第|S|位，每次匹配最小的即可，保证得到的是最小的。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char chr[maxn];int L;
struct SAM
{
    int fa[maxn],ch[maxn][],maxlen[maxn],tot,last;
    void init()
    {
        tot=last=; maxlen[]=fa[]=;
        memset(ch[],,sizeof(ch[]));
    }
    void add(int x)
    {
          int np=++tot,p=last;last=np;
          maxlen[np]=maxlen[p]+;
          memset(ch[np],,sizeof(ch[np]));
          while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
          if(!p) fa[np]=;
          else {
                int q=ch[p][x];
                if(maxlen[q]==maxlen[p]+) fa[np]=q;
                else {
                    int nq=++tot;
                    memcpy(ch[nq],ch[q],sizeof(ch[q]));
                    fa[nq]=fa[q],fa[np]=fa[q]=nq;
                    maxlen[nq]=maxlen[p]+;
                    while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
                }
         }
    }
    void solve()
    {
        int Now=;
        rep(i,,L-)
          rep(j,,){
            if(ch[Now][j]) {
                Now=ch[Now][j];break;
            }
        }
        printf("%d\n",maxlen[Now]-L+);
    }
}S;
int main()
{
    int n;
    while(~scanf("%d",&n)){
        while(n--){
           S.init();
           scanf("%s",chr);
           L=strlen(chr);
           rep(i,,L-) S.add(chr[i]-'a');
           rep(i,,L-) S.add(chr[i]-'a');
           S.solve();
        }
    }
    return ;
}

例题二：SPOJ - LCSLongest Common Substring

题意：给定字符串S，T，求最长公共子串。|S|,|T|<25e4

思路：SAM的基操，一个串建立SAM，一个串跑。

注意这个跑的时候，其长度是需要记录的，因为自动机里面记录的长度是“集合”的最长长度，而我们匹配的时候是对应的集合中的一个。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn];
struct SAM
{
    int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last;
    void init()
    {
        cnt=; last=;
        memset(ch[],,sizeof(ch[]));
    }
    void add(int x)
    {
       int np=++cnt,p=last;
       last=np; maxlen[cnt]=maxlen[p]+;
       memset(ch[np],,sizeof(ch[np]));
       while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
       if(!p) fa[np]=;
       else {
         int q=ch[p][x];
         if(maxlen[q]==maxlen[p]+) fa[np]=q;
         else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q], fa[q]=fa[np]=nq;
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
         }
      }
    }
    int match()
    {
       int np=,len=,ans=,N;
       scanf("%s",c+); N=strlen(c+);
       rep(i,,N){
          int x=c[i]-'a';
          while(np&&!ch[np][x]) np=fa[np],len=maxlen[np];
          if(!np) np=,len=;
          if(ch[np][x]) np=ch[np][x],len++;
          ans=max(ans,len);
       }
       return ans;
    }
}T;
int main()
{
    int N,Q,K;
    scanf("%s",c+); N=strlen(c+);
    T.init();
    rep(i,,N) T.add(c[i]-'a');
    printf("%d\n",T.match());
    return ;
}

例题三：SPOJ - LCS2Longest Common Substring II

题意：给定最多N(N<10)个串，求最长公共字串。|每个串|<1e5。

思路：可以和上一题一样，用一个建SAM，剩下的去匹配。

这里也可以用另外的一种方法：广义后缀自动机。 这个东西表示，多个串，我丢到一个自动机里，这样的话会会节省很多空间。每个串丢进去之前把last设为1；

而且更方便的是，我们可以一遍插入，一遍更新，如果一个点被更新了N次，则属于公共子串。  由于每个点最多被更新一次，所以复杂度是线性的。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn]; int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last,T,ans;
int vis[maxn],num[maxn];
void insert(int x)
{
    int np=++cnt,p=last;
    last=np; maxlen[cnt]=maxlen[p]+;
    memset(ch[np],,sizeof(ch[np]));
    while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
    if(!p) fa[np]=;
    else {
        int q=ch[p][x];
        if(maxlen[q]==maxlen[p]+) fa[np]=q;
        else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q], fa[q]=fa[np]=nq; vis[nq]=vis[q]; num[nq]=num[q];
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
        }
    }
    while(np&&vis[np]!=T) vis[np]=T,num[np]++,np=fa[np];
}
int main()
{
    int N; cnt=; memset(ch[],,sizeof(ch[]));
    while(~scanf("%s",c+)) {
        N=strlen(c+); last=; T++;
        rep(i,,N) insert(c[i]-'a');
    }
    rep(i,,cnt) if(num[i]==T) ans=max(ans,maxlen[i]);
    printf("%d\n",ans);
    return ;
}

例题四：SPOJ - NSUBSTRSubstrings

题意：给定字符串S。对于i=1到|S|，输出出现最多次数的长度为i字串出现的次数。 |S|<25e4

思路：先得到自动机，然后topo得到所有字串的出现次数。 注意一点就是，长度越短，对应的出现次数一定不减。我们可以从长到短依次更新即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn];int ans[maxn];
struct SAM
{
    int ch[maxn][],fa[maxn],maxlen[maxn];
    int a[maxn],b[maxn],sz[maxn],cnt,last;
    void init()
    {
        cnt=last=;
        memset(ch[],,sizeof(ch[]));
    }
    void add(int x)
    {
      int np=++cnt,p=last; sz[np]=;
      last=np; maxlen[cnt]=maxlen[p]+;
      memset(ch[np],,sizeof(ch[np]));
      while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
      if(!p) fa[np]=;
      else {
        int q=ch[p][x];
        if(maxlen[q]==maxlen[p]+) fa[np]=q;
        else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q], fa[q]=fa[np]=nq;
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
        }
      }
   }
   void sort()
   {
      rep(i,,cnt) a[i]=;
      rep(i,,cnt) a[maxlen[i]]++;
      rep(i,,cnt) a[i]+=a[i-];
      rep(i,,cnt) b[a[maxlen[i]]--]=i;
      for(int i=cnt;i>=;i--) sz[fa[b[i]]]+=sz[b[i]];
      rep(i,,cnt) ans[maxlen[i]]=max(ans[maxlen[i]],sz[i]);
      for(int i=cnt;i>=;i--) ans[i]=max(ans[i],ans[i+]);
   }
}T;
int main()
{
    int N;
    scanf("%s",c+); N=strlen(c+);
    T.init();
    rep(i,,N) T.add(c[i]-'a');
    T.sort();
    rep(i,,N) printf("%d\n",ans[i]);
    return ;
}

例题五：SPOJ - SUBLEXLexicographical Substring Search

题意：给定字符串S，现在将所有不同字串按字典序排序后，询问字典序第K大的字串，Q次询问。 |S|<9e4，Q<500, K<2^31

思路：最先的肯定的'a'开头的，然后是'b'开头的....，如果‘a’开头的大于等于K个，然后往‘a’的子树里走，即第一位是‘a’； 否则，K-=sum[a]，继续看'b'....

直到K<=0；   所以我们现在只要得到topo，倒序每个字符的子树大小即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn];
struct SAM
{
    int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last;
    int a[maxn],b[maxn],sz[maxn];
    void init()
    {
       cnt=; last=; memset(ch[],,sizeof(ch[]));
    }
    void add(int x)
    {
       int np=++cnt,p=last; //sz[np]=1;
       last=np; maxlen[cnt]=maxlen[p]+;
       memset(ch[np],,sizeof(ch[np]));
       while(p&&!ch[p][x])ch[p][x]=np,p=fa[p];
       if(!p) fa[np]=;
       else {
          int q=ch[p][x];
          if(maxlen[q]==maxlen[p]+) fa[np]=q;
          else {
             int nq=++cnt; maxlen[nq]=maxlen[p]+;
             memcpy(ch[nq],ch[q],sizeof(ch[q]));
             fa[nq]=fa[q], fa[q]=fa[np]=nq;
             while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
          }
       }
    }
    void sort()
    {
       rep(i,,cnt) sz[i]=;//maxlen[i]-maxlen[fa[i]];
       rep(i,,cnt) a[i]=;
       rep(i,,cnt) a[maxlen[i]]++;
       rep(i,,cnt) a[i]+=a[i-];
       rep(i,,cnt) b[a[maxlen[i]]--]=i;
       for(int i=cnt;i>=;i--){
         rep(j,,) if(ch[b[i]][j])
           sz[b[i]]+=sz[ch[b[i]][j]];
       }
   }
   void dfs(int np,int K)
   {
      if(np>) K-=; if(K<=) return ;
      rep(i,,){
        if(!ch[np][i]) continue;
        if(sz[ch[np][i]]<K) K-=sz[ch[np][i]];
        else{
            putchar('a'+i);
            dfs(ch[np][i],K);
            return ;
        }
      }
   }
}T;
int main()
{
    int N,Q,K;
    scanf("%s",c+); N=strlen(c+);
    T.init();
    rep(i,,N) T.add(c[i]-'a');
    T.sort();
    scanf("%d",&Q);
    while(Q--){
        scanf("%d",&K);
        T.dfs(,K);
        putchar('\n');
    }
    return ;
}

例题六：HDU - 4622Reincarnation

题意：给定字符串S，Q次询问区间不同子串。|S|<1000; Q<10000;

思路：左端点一样的一起搞就行了。 |S|次建立自动机，O(|S|^2)；

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int ch[maxn<<][],fa[maxn<<],ans[maxn*],maxlen[maxn<<],cnt,last,sum; char c[maxn];
struct in{
    int L,R,id;
    bool friend operator <(in w,in v){
        if(w.L==v.L) return w.R<v.R;
        return w.L<v.L;
    }
}s[maxn*];
void insert(int x)
{
    int np=++cnt,p=last; last=np;
    maxlen[np]=maxlen[p]+;
    memset(ch[np],,sizeof(ch[np]));
    while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
    if(!p) fa[np]=;
    else{
        int q=ch[p][x];
        if(maxlen[q]==maxlen[p]+) fa[np]=q;
        else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            fa[nq]=fa[q]; fa[q]=fa[np]=nq;
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
        }
    } sum+=maxlen[np]-maxlen[fa[np]];
}
int main()
{
    int T,N,Q;
    scanf("%d",&T);
    while(T--){
        scanf("%s",c+); N=strlen(c+);
        scanf("%d",&Q);
        rep(i,,Q) scanf("%d%d",&s[i].L,&s[i].R),s[i].id=i;
        sort(s+,s+Q+);
        rep(i,,Q){
            last=; cnt=; sum=;
            memset(ch[],,sizeof(ch[]));
            int pos=i;
            rep(j,s[i].L,N){
                insert(c[j]-'a');
                while(s[pos].L==s[i].L&&j==s[pos].R&&pos<=Q) ans[s[pos].id]=sum,pos++;
            }
            i=pos-;
        }
        rep(i,,Q) printf("%d\n",ans[i]);
    }
    return ;
}

例题七：HDU - 4436str2int

题意：给定N个数字串，求所有不同子串10进制下的和，结果膜2012。

思路：建立广义后缀自动机，然后从根节点，顺序遍历所有节点即可，num为到达节点的个数，val为节点的前缀和。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int Mod=;
char c[maxn];
struct SAM{
    int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last;
    int a[maxn],b[maxn],ans,num[maxn],val[maxn];
    void init()
    {
        cnt=; memset(ch[],,sizeof(ch[]));
    }
    int add(int x)
    {
       int np=++cnt,p=last; last=np;
       maxlen[np]=maxlen[p]+;memset(ch[np],,sizeof(ch[np]));
       while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
       if(!p) fa[np]=;
       else {
         int q=ch[p][x];
         if(maxlen[q]==maxlen[p]+) fa[np]=q;
         else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            fa[nq]=fa[q]; fa[q]=fa[np]=nq;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
         }
       }
    }
   void sort()
   {
     rep(i,,cnt) a[i]=;
     rep(i,,cnt) a[maxlen[i]]++;
     rep(i,,cnt) a[i]+=a[i-];
     rep(i,,cnt) b[a[maxlen[i]]--]=i;
   }
   void solve()
   {
      sort();
      rep(i,,cnt) num[i]=val[i]=;
      num[]=; ans=;
      rep(i,,cnt){
         int p=b[i];
         rep(j,,){
            if((i==&&j==)||!ch[p][j]) continue;
            (num[ch[p][j]]+=num[p])%=Mod;
            (val[ch[p][j]]+=val[p]*+num[p]*j)%=Mod;
        }
        (ans+=val[p])%=Mod;
      }
    }
}T;
int main()
{
    int N,L;
    while(~scanf("%d",&N)){
        T.init();
        rep(i,,N) {
            scanf("%s",c+);
            L=strlen(c+); T.last=;
            rep(j,,L) T.add(c[j]-'');
        }
        T.solve();
        printf("%d\n",T.ans);
    }
    return ;
}

例题八：CodeForces - 235CCyclical Quest

题意：给定字符串S，Q次询问，每次询问给定字符串x，问S中有多少子串，可以通过循环同构=x；|x总和|<1e6。

思路：先把S建立自动机，然后topt得到每个节点的次数。 然后再想办法处理匹配，显然x需要每个点作为起点跑一遍自动机，然后重复的指统计一次。 但是这样复杂度是O(x^2)； 正确的方法是，把x加倍，然后在自动机上面跑，如果跑得的长度大于|x|，则失配，向fa跑。 整个过程中跑到的点只统计一次。 复杂度是线性的。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
char c[maxn];
struct SAM{
    int ch[maxn][],fa[maxn],maxlen[maxn],cnt,last;
    int a[maxn],b[maxn],sz[maxn],val[maxn],vis[maxn],ans;
    SAM(){cnt=;last=;}
    int add(int x)
    {
       int np=++cnt,p=last; last=np;
       maxlen[np]=maxlen[p]+; sz[np]=;
       while(p&&!ch[p][x]) ch[p][x]=np,p=fa[p];
       if(!p) fa[np]=;
       else {
         int q=ch[p][x];
         if(maxlen[q]==maxlen[p]+) fa[np]=q;
         else {
            int nq=++cnt; maxlen[nq]=maxlen[p]+;
            fa[nq]=fa[q]; fa[q]=fa[np]=nq;
            memcpy(ch[nq],ch[q],sizeof(ch[q]));
            while(p&&ch[p][x]==q) ch[p][x]=nq,p=fa[p];
         }
       }
    }
    void sort()
    {
      rep(i,,cnt) a[i]=;
      rep(i,,cnt) a[maxlen[i]]++;
      rep(i,,cnt) a[i]+=a[i-];
      rep(i,,cnt) b[a[maxlen[i]]--]=i;
      for(int i=cnt;i>=;i--) sz[fa[b[i]]]+=sz[b[i]];
    }
    int match(int T)
    {
        scanf("%s",c+);
        int L=strlen(c+);
        rep(i,,L) c[i+L]=c[i];
        int np=,len=,ans=;
        rep(i,,L+L){
            int x=c[i]-'a';
            if(ch[np][x]) np=ch[np][x],len++;
            else {
               while(np&&!ch[np][x]) np=fa[np],len=maxlen[np];
               if(!np) np=,len=;
               if(ch[np][x]) np=ch[np][x],len++;
            }
            while(len>L){
                if(len->maxlen[fa[np]]) len--;
                else np=fa[np],len=maxlen[np];
                //注意这里，截去头部的两种情况。
            }
            if(len==L&&vis[np]!=T) ans+=sz[np],vis[np]=T;
        }
        return ans;
    }
}T;
int main()
{
    int N,L,Cas=;
    scanf("%s",c+); L=strlen(c+);
    rep(j,,L) T.add(c[j]-'a');
    T.sort();
    scanf("%d",&N);
    while(N--){
        int ans=T.match(++Cas);
        printf("%d\n",ans);
    }
    return ;
}

本来还有一些经典的例题，但是感觉没必要放太多例题。。。 上面的题都放到VJ-后缀自动机上面了

明天又要开始打gym了，后缀数组会尽量更新。 02-19------分界线------

后缀数组

上面我们说到，后缀自动机并不是万能的，虽然后缀自动机优美，简洁，强大......（超喜欢SAM）下面我会尽可能的和后缀自动机做比较，如果可以，找一些后缀数组可以实现，后缀自动机不太好做的题。

有的时候我们得用后缀数组来解决问题。 因为后缀数组是排序后的数组，可以结合线段树，二分，单调队列...来解决一些RMQ问题。

认识：

1，sa数组：按照字典序排序后的数组，第i位表示第i大的后缀对应在字符串中的下标。

2，ht数组：height数组，表示排序后和前一个的最长公共前缀。

3，rank数组：字符串后缀的排名。上面两个数组是针对的排序后，rank针对的字符串本身。

在求出sa和rank之后，其中sa和rank可以互相转化，他们一一对应，因为后缀的长度都不同，所以不可能有字典序相同的后缀，所以sa对应1到N。

排序：

        基数排序，倍增。 对于字符串S，假如只有小写字母，对应了1到26；

一开始，我们对长度为1的字符串进行基数排序，这个时候sa数组对应1到N，而Rank数组对应1到26，显然不够一一对应，即排序未完成；

所以我们按照长度为2的继续排序，那么他们可以把后面一位当作第二关键字.....直到Rank对应1到N，说明排序完毕。

height数组功能：

假设要求suf(i)和suf(j)的最长公共前缀LCP，假设rank[i]<rank[j]，那么ans=min(ht[rank[i]+1],ht[rank[i]+2]....ht[j]);

这是显然的，因为我们已经按字典序排序了。   而区间最小值我们可以ST预处理，O（1）查询。

本质不同的子串数量：

1，回文树的本质不同的回文串：就是数组大小，即tot。

2，后缀自动机的本质不同的子串：集合大小之和，即Σ(maxlen[i]-maxlen[fa[i]])。

3，后缀数组：我们统计每一个下标作为开头的子串的贡献。 对于下标i, S[i,i]; S[i,i+1],S[i,i+2]....S[i,len];个数为len-i+1，然后我们知道了它和之前的重复数量，去重就是减去ht[rank[i]]；

两个串的最长公共子串：

求S和T的最长公共子串，我们把他们连接S+‘&’+T，这样的话就对应了|S|+|T|+1个后缀，求后缀数组。 如果sa[i]和sa[i-1]对应的下标分别是S和T，则可以用ht[i]更新答案。  因为区间越长，min(height)越小。

实现：cntA，A统计第一关键字，cntB，B统计第二关键字。 tsa是按照第二关键字排序的结果，然后把用来排第一关键字。

void getsa()
    {
        N=strlen(ch+);
        rep(i,,) cntA[i]=;//注意这里是字符范围，不是N
        rep(i,,N) cntA[ch[i]]++;
        rep(i,,) cntA[i]+=cntA[i-];
        rep2(i,N,) sa[cntA[ch[i]]--]=i;
        Rank[sa[]]=;
        rep(i,,N) Rank[sa[i]]=Rank[sa[i-]]+(ch[sa[i]]==ch[sa[i-]]?:);
        for(int l=;Rank[sa[N]]<N;l<<=){
            rep(i,,N) cntA[i]=cntB[i]=;
            rep(i,,N) cntA[A[i]=Rank[i]]++;
            rep(i,,N) cntB[B[i]=i+l<=N?Rank[i+l]:]++;
            rep(i,,N) cntA[i]+=cntA[i-],cntB[i]+=cntB[i-];
            rep2(i,N,) tsa[cntB[B[i]]--]=i;
            rep2(i,N,) sa[cntA[A[tsa[i]]]--]=tsa[i];
            Rank[sa[]]=;
            rep(i,,N) Rank[sa[i]]=Rank[sa[i-]]+(A[sa[i]]==A[sa[i-]]&&B[sa[i]]==B[sa[i-]]?:);
        }
    }

求height数组：利用相邻关系，有height[rank[i]] ≥ height[rank[i-1]]-1

    void getht()
    {
        for(int i=,j=;i<=N;i++){
            if(j) j--;
            while(ch[i+j]==ch[sa[Rank[i]-]+j]) j++;
            ht[Rank[i]]=j;
        }
    }

（目前暂未出现后缀自动机不能实现的功能.....其他功能请看例题。）