后缀自动机：

一、模板：
洛谷P3804

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1000100;
char str[maxn];

int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],fa[maxn<<1];
    int len[maxn<<1],sum[maxn<<1];

    void init(void)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];
        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp;
        sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--)
            sum[fa[y[i]]]+=sum[y[i]];
        return ;

    }

    void creat(void)
    {
        int len=strlen(str);

        init();
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');
        _count();

        return ;
    }
}sam;


int main(void)
{
    scanf("%s",str);
    sam.creat();
    ll maxx=0;
    for(int i=1;i<=sam.cnt;i++)
        if(sam.sum[i]>1)
            maxx=max((ll)sam.sum[i]*sam.len[i],maxx);

    printf("%lld\n",maxx);
    return 0;
}

二、string string string HDU - 6194 ：
求出sum数组即可，判断是否与k相等，若相等，则节点i，代表的字符串都符合题意，求出节点i代表的字符串的个数即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=100100;
char str[maxn];

int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        return ;
    }

    void creat(void)
    {
        int len=strlen(str);

        init((len+5)*2);
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');
        _count();

        return ;
    }
}sam;

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int k;
        scanf("%d%s",&k,str);
        sam.creat();
        ll ans=0;
        for(int i=1;i<=sam.cnt;i++)
        {
            if(sam.sum[i]==k)
            {
                ans+=(sam.len[i]-sam.len[sam.fa[i]]);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

三、后缀数组一·重复旋律 HihoCoder - 1403：
至少出现k次的可重叠最长子串：
求出sum数组，sum≥k时，用len【i】更新最大值即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=20100;
char str[maxn];

int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][101],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        return ;
    }

    void creat(int n)
    {

        init((n+5)*2);
        int t;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&t);
            _insert(t);
        }
        _count();

        return ;
    }
}sam;

int main(void)
{
    int n,k;
    scanf("%d%d",&n,&k);
    sam.creat(n);
    int maxx=0;
    for(int i=1;i<=sam.cnt;i++)
        if(sam.sum[i]>=k) maxx=max(maxx,sam.len[i]);

    printf("%d\n",maxx);
    return 0;
}

四、两个串的最长公共子串，已用后缀数组解决过，现在用后缀自动机解决：
parents树上fa（i）是i的后缀
直接跑nt即可：
Longest Common Substring SPOJ - LCS：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=250100;
char str[maxn];
char str1[maxn];

int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        return ;
    }

    void creat(void)
    {

        int len=strlen(str);
        init((len+5)*2);
        int t;
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');

        //_count();

        return ;
    }
    int fi(void)
    {
        int lenn=strlen(str1);
        int ans=0;
        int res=0;
        int now=1;
        for(int i=0;i<lenn;i++)
        {
            if(nt[now][str1[i]-'a']) res++,now=nt[now][str1[i]-'a'];
            else
            {
                while(now&&!nt[now][str1[i]-'a']) now=fa[now];
                if(!now) res=0,now=1;
                else res=len[now]+1,now=nt[now][str1[i]-'a'];
            }
            ans=max(ans,res);
        }
        return ans;
    }
}sam;

int main(void)
{
    while(scanf("%s%s",str,str1)!=EOF)
    {
        sam.creat();
        printf("%d\n",sam.fi());
    }

    return 0;
}

五、 Longest Common Substring II
多个串的最长公共子串：对其中一个串建立后缀自动机，其他串分别与这个串匹配，取每个匹配位置 i 的最小值。
对最终答案所有 i 取最大值。
在更新 i 的过程中，有可能子节点已更新但是父节点没有更新，实际上父节点dp应该是有值的，我们按照拓扑序更新一下父节点即可。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=120100;
char str[maxn];
char str1[maxn];
int dp[maxn<<1];
int ans[maxn<<1];

int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        return ;
    }

    void creat(void)
    {

        int len=strlen(str);
        init((len+5)*2);
        int t;
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');

        _count();

        return ;
    }
    void fi(void)
    {
        memset(dp,0,sizeof(dp));
        int lenn=strlen(str1);
        int res=0;
        int now=1;
        for(int i=0;i<lenn;i++)
        {
            if(nt[now][str1[i]-'a']) res++,now=nt[now][str1[i]-'a'];
            else
            {
                while(now&&!nt[now][str1[i]-'a']) now=fa[now];
                if(!now) res=0,now=1;
                else res=len[now]+1,now=nt[now][str1[i]-'a'];
            }
            dp[now]=max(dp[now],res);
        }

        for(int i=cnt;i>=1;i--)
            dp[fa[y[i]]]=max(dp[fa[y[i]]],min(dp[y[i]],len[fa[y[i]]]));
        for(int i=1;i<=cnt;i++)
            ans[i]=min(ans[i],dp[i]);
        return ;
    }
}sam;

int main(void)
{
    scanf("%s",str);
    sam.creat();
    for(int i=1;i<=sam.cnt;i++)
        ans[i]=sam.len[i];
    while(scanf("%s",str1)!=EOF)
    {
        sam.fi();
    }
    int maxx=0;
    for(int i=1;i<=sam.cnt;i++)
        maxx=max(maxx,ans[i]);

    printf("%d\n",maxx);


    return 0;
}

六、长度为 i 的串出现的最多的出现次数：
对于每个出现次数 i，维护这个节点出现所有子串长度的最大值即可：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=250100;
char str[maxn];
char str1[maxn];


int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        return ;
    }

    void creat(void)
    {

        int len=strlen(str);
        init((len+5)*2);
        int t;
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');

        _count();

        return ;
    }

}sam;

struct node
{
    int maxx;
    int l,r;
    int laz=0;
}tree[maxn<<2];

void bulid(int l,int r,int cnt)
{
    tree[cnt].l=l,tree[cnt].r=r;
    if(l==r)
    {
        tree[cnt].maxx=0;
        tree[cnt].laz=0;
        return ;
    }

    int mid=(l+r)>>1;
    bulid(l,mid,cnt<<1);
    bulid(mid+1,r,cnt<<1|1);
    tree[cnt].maxx=max(tree[cnt<<1].maxx,tree[cnt<<1|1].maxx);
    return ;
}

void pushdown(int cnt)
{
    if(tree[cnt].laz)
    {
        tree[cnt<<1].laz=max(tree[cnt].laz,tree[cnt<<1].laz);
        tree[cnt<<1|1].laz=max(tree[cnt].laz,tree[cnt<<1|1].laz);
        tree[cnt<<1].maxx=max(tree[cnt].laz,tree[cnt<<1].maxx);
        tree[cnt<<1|1].maxx=max(tree[cnt].laz,tree[cnt<<1|1].maxx);
        tree[cnt].laz=0;
    }
    return ;
}

void change(int l,int r,int val,int cnt)
{
    if(l<=tree[cnt].l&&tree[cnt].r<=r)
    {
        tree[cnt].maxx=max(tree[cnt].maxx,val);
        tree[cnt].laz=max(tree[cnt].laz,val);
        return ;
    }
    pushdown(cnt);
    if(l<=tree[cnt<<1].r) change(l,r,val,cnt<<1);
    if(r>=tree[cnt<<1|1].l) change(l,r,val,cnt<<1|1);

    tree[cnt].maxx=max(tree[cnt<<1].maxx,tree[cnt<<1|1].maxx);
}


int ask(int pos,int cnt)
{
    if(tree[cnt].l==tree[cnt].r)
    {
        return tree[cnt].maxx;
    }
    pushdown(cnt);
    if(pos<=tree[cnt<<1].r) return ask(pos,cnt<<1);
    else return ask(pos,cnt<<1|1);
}


int main(void)
{
    while(scanf("%s",str)!=EOF)
    {
        sam.creat();
        int lenn=strlen(str);
        bulid(1,lenn,1);
        for(int i=1;i<=sam.cnt;i++)
        {
            int l=sam.len[sam.fa[i]]+1;
            int r=sam.len[i];
            if(l>r) continue;
            //cout<<sam.len[sam.fa[i]]+1<<" "<<sam.len[i]<<" "<<sam.sum[i]<<endl;
            change(l,r,sam.sum[i],1);
        }

        for(int i=1;i<=lenn;i++)
        {
            printf("%d\n",ask(i,1));
        }
    }
    return 0;


    return 0;
}

七、找字典序第k小子串，其中子串不重复：
处理trie树，跑出所有子串，然后找就可以了：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=90100;
char str[maxn];
char str1[maxn];


int x[maxn<<1],y[maxn<<1];
struct Sam
{
    int last,cnt;
    int nt[maxn<<1][26],len[maxn<<1];
    int fa[maxn<<1],sum[maxn<<1];
    int ans[maxn<<1];

    void init(int n)
    {
        last=1;
        cnt=1;
        fa[1]=0;
        len[1]=0;

        for(int i=0;i<=n;i++)
        {
            fa[i]=0;
            len[i]=0;
            sum[i]=0;
            ans[i]=0;
            memset(nt[i],0,sizeof(nt[i]));
        }
    }

    void _insert(int c)
    {
        int nowp=++cnt,p=last;
        len[nowp]=len[last]+1;

        while(p&&!nt[p][c]) nt[p][c]=nowp,p=fa[p];

        if(!p) fa[nowp]=1;
        else
        {
            int q=nt[p][c];
            if(len[q]==len[p]+1) fa[nowp]=q;
            else
            {
                int nowq=++cnt;
                len[nowq]=len[p]+1;
                memcpy(nt[nowq],nt[q],sizeof(nt[q]));

                fa[nowq]=fa[q];
                fa[nowp]=fa[q]=nowq;

                while(p&&nt[p][c]==q) nt[p][c]=nowq,p=fa[p];
            }
        }
        last=nowp,sum[last]=1;
        return ;
    }

    void _count(void)
    {
        memset(x,0,sizeof(x));
        for(int i=1;i<=cnt;i++) x[len[i]]++;
        for(int i=1;i<=cnt;i++) x[i]+=x[i-1];
        for(int i=1;i<=cnt;i++) y[x[len[i]]--]=i;
        for(int i=cnt;i>=1;i--) sum[fa[y[i]]]+=sum[y[i]];
        for(int i=cnt;i>=1;i--)
        {
            ans[y[i]]=1;
            for(int j=0;j<26;j++)
                ans[y[i]]+=ans[nt[y[i]][j]];
        }
        return ;
    }

    void creat(void)
    {

        int len=strlen(str);
        init((len+5)*2);
        int t;
        for(int i=0;i<len;i++)
            _insert(str[i]-'a');

        _count();

        return ;
    }

}sam;



int main(void)
{
    while(scanf("%s",str)!=EOF)
    {
        sam.creat();
        int t,kk;
        scanf("%d",&t);
        for(int i=1;i<=t;i++)
        {
            scanf("%d",&kk);
            int pp=1;
            while(kk)
            {
                for(int j=0;j<26;j++)
                {
                    if(sam.nt[pp][j])
                    {
                        if(sam.ans[sam.nt[pp][j]]>=kk)
                        {
                            putchar(j+'a');
                            pp=sam.nt[pp][j];
                            kk--;
                            break;
                        }
                        else kk-=sam.ans[sam.nt[pp][j]];
                    }
                }
            }

            putchar('\n');
        }

    }

    return 0;
}