后缀自动机（SAM）+广义后缀自动机（GSA）

经过一顿操作之后竟然疑似没退役0 0

你是XCPC选手吗？我觉得我是！

稍微补一点之前丢给队友的知识吧，除了数论以外都可以看看，为Dhaka和新队伍做点准备...

不错的零基础教程见 IO WIKI - 后缀自动机，这篇就从自己的角度总结一下吧，感觉思路总是和别人不一样...尽量用我比较能接受的语言和逻辑重新组织一遍。

注意：在本文中，字符串的下标从1开始。

目前的 SAM 模板：

const int N=100005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;

目前的 GSA 模板：

typedef pair<int,int> pii;

const int N=1000005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct GeneralSuffixAutomaton
{
    int sz; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(int,char)
    
    GeneralSuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        sz=0;
    }
    
    //向trie树上插入一个字符串 
    void insert(char *s,int n)
    {
        for(int i=1,cur=0;i<=n;i++)
        {
            int c=s[i]-'a';
            if(!nxt[cur][c])
                nxt[cur][c]=++sz;
            cur=nxt[cur][c];
        }
    }
    
    //扩展GSA，对于lst的c转移进行扩展 
    int extend(int lst,int c)
    {
        int cur=nxt[lst][c];
        len[cur]=len[lst]+1;
        
        int p=link[lst];
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                for(int i=0;i)
                    nxt[clone][i]=len[nxt[q][i]]?nxt[q][i]:0;
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        return cur;
    }
    
    //基于trie树建立GSA
    void build()
    {
        queue Q;
        for(int i=0;i)
            if(nxt[0][i])
                Q.push(pii(0,i));
        
        while(!Q.empty())
        {
            pii tmp=Q.front();
            Q.pop();
            
            int cur=extend(tmp.first,tmp.second);
            for(int i=0;i)
                if(nxt[cur][i])
                    Q.push(pii(cur,i));
        }
    } 
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}gsa;

简单的目录：

OI WIKI - SAM - 正确性证明 以及 OI WIKI - SAM - 对操作数为线性的证明。不过对于抄板子不是那么关键。

为了便于感性的理解，我们不妨举一个扩展 SAM 的过程中最复杂的 Case #3 的例子。

字符串 $s=abb$，当仅扩展了 $ab$ 与扩展完了 $abb$ 时，SAM 的结构分别如下：

可以看出，做一次 Case #3 的扩展相当于对于一个 endpos 等价类（如图中的 $\{b,ab\}$）做拆分。更深入的分析就不展开了。


由于 SAM 中所有状态所表示的字符串都是互不相同的，所以本质不同的子串数量就是$\sum_{state}\mathrm{len}(state)-\mathrm{minlen}(state)+1$，即把每个状态中包含的字符串数量全部加起来。

例题：LOJ2033 「SDOI2016」生成魔咒

#include 
#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N=100005;
const int C=26; //注意检查字符集大小！

ll ans=0;

struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    //int nxt[N<<1][C];
    map<int,int> nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                //memcpy(nxt[clone],nxt[q],C*4);
                nxt[clone]=nxt[q];
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
        ans+=len[cur]-len[link[cur]];
    }
}sam;

int n;
int a[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    
    for(int i=1;i<=n;i++)
        sam.extend(a[i]),printf("%lld\n",ans);
    return 0;
}

另一方面，某一子串的出现次数就等于其 $\mathrm{endpos}$ 集合的大小。根据性质“每个状态的 $\mathrm{endpos}$ 集合为其在 parent 树中子树 $\mathrm{endpos}$ 集合的并集”，我们对于 $s[1:i]$ 所在状态赋为 $1$，其余状态为 $0$，然后通过在 parent 树上 dfs 求子树中 $1$ 的个数即可。

例题：洛谷P3804 【模板】后缀自动机 (SAM)

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N=1000005;
const int C=26; //注意检查字符集大小！

struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;

int n;
char s[N];

int cnt[N<<1];

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    
    for(int i=1;i<=n;i++)
        sam.extend(s[i]-'a'),cnt[sam.lst]=1;
    
    sam.sort();
    
    ll ans=0;
    for(int i=sam.sz;i>=1;i--)
    {
        int id=sam.id[i];
        if(cnt[id]>1)
            ans=max(ans,1LL*cnt[id]*sam.len[id]);
        
        cnt[sam.link[id]]+=cnt[id];
    }
    printf("%lld\n",ans);
    return 0;
}

在以上的实现中，并没有显式地对于 parent 树进行 dfs，而是将所有状态拓扑排序后按序处理。进行拓扑排序的策略并不复杂，我们只需要按照 $\mathrm{len}(state)$ 进行一趟桶排，这样即可保证祖先（$\mathrm{len}$ 较小）一定排在子孙（$\mathrm{len}$ 较大）的前面，此时倒序即为一个合法的拓扑排序。

int id[N<<1];

//构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
void sort()
{
    static int bucket[N<<1];
    
    memset(bucket,0,sizeof(bucket));
    for(int i=1;i<=sz;i++)
        bucket[len[i]]++;
    for(int i=1;i<=sz;i++)
        bucket[i]+=bucket[i-1];
    for(int i=1;i<=sz;i++)
        id[bucket[len[i]]--]=i;
}

2. 字典序第 K 大子串（SAM 上 DP）

我们先考虑本质相同的子串仅计算一次的情况。刚刚在计算本质不同子串数量的时候，我们利用状态的性质解决了，但实际上还有一个在 SAM 上 DP 的做法。

有这样的一个结论：一个字符串本质不同的子串数量，相当于在 SAM 上通过 $\mathrm{nxt}$ 转移产生的路径数量。我们尝试理解这个结论。首先，这样的计数一定不会少算（有子串没被算到），因为每个本质不同的子串都会在 SAM 上存在唯一对应的路径；同时，这个计数也不会多算（算到多余的子串），因为 SAM 仅接受模式串的子串。

利用这个结论，我们直接利用 DP 计算从每个状态出发的路径数量即可（由于 $\mathrm{nxt}$ 转移构成的图是一个 DAG，我们仍然可以通过令 $\mathrm{len}$ 从小到大来获得一个正拓扑序）。DP 的转移方程为 $path[x]=1+\sum_{y=\mathrm{nxt}_x(c_i)}path[y]$，需要按照逆拓扑序依次计算。

对于本质相同的子串计算出现次数的情况，将上面转移方程中的 $1$ 替换成 $cnt[x]$ 即可。

那么求字典序第 $K$ 大子串，只需要从 $state_0$ 开始贪心，每次选取最小的前缀路径数量大于等于 $K$ 的转移即可（原理同线段树上二分，只不过 SAM 上每个状态有字符集大小的分叉）。

例题：LOJ2102 「TJOI2015」弦论

#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N=500005;
const int C=26; //注意检查字符集大小！

struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;

int n;
char s[N];
int type,K;

int cnt[N<<1];
ll path[N<<1][2];

int main()
{
    scanf("%s",s+1);
    scanf("%d%d",&type,&K);
    n=strlen(s+1);
    
    for(int i=1;i<=n;i++)
        sam.extend(s[i]-'a'),cnt[sam.lst]=1;
    
    sam.sort();
    
    for(int i=sam.sz;i>=0;i--)
    {
        int id=sam.id[i];
        
        path[id][0]=1,path[id][1]=cnt[id];
        for(int j=0;j)
        {
            int nxt=sam.nxt[id][j];
            if(nxt)
                for(int k=0;k<2;k++)
                    path[id][k]+=path[nxt][k];
        }
        if(id!=-1)
            cnt[sam.link[id]]+=cnt[id];
    }
    
    if(path[0][type]-cnt[0]<K)
        printf("-1\n");
    else
    {
        int cur=0;
        while(K)
        {
            for(int i=0;i)
            {
                int nxt=sam.nxt[cur][i];
                if(!nxt)
                    continue;
                
                if(path[nxt][type]>=K)
                {
                    cur=nxt,putchar('a'+i);
                    K-=(type?cnt[cur]:1);
                    break;
                }
                K-=path[nxt][type];
            }
        }
    }
    return 0;
}

3. 两个字符串的最长公共子串（SAM 上匹配）

对于 $s,t$ 两个字符串，对于 $s$ 串建立 SAM，$t$ 在这个 SAM 上进行匹配，失配时跳 $\mathrm{link}$。实现上和 AC 自动机差不多。

例题：SPOJ-LCS Longest Common Substring

#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N=250005;
const int C=26; //注意检查字符集大小！

struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(char)，并使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=sz=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;

int n,m;
char s[N],t[N];

int main()
{
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1),m=strlen(t+1);
    
    for(int i=1;i<=n;i++)
        sam.extend(s[i]-'a');
    
    int ans=0,cur=0,len=0;
    for(int i=1;i<=m;i++)
    {
        int p=cur;
        while(p!=-1 && !sam.nxt[p][t[i]-'a'])
            p=sam.link[p],len=sam.len[p];
        
        if(p!=-1)
            cur=sam.nxt[p][t[i]-'a'],len++;
        else
            cur=len=0;
        
        ans=max(ans,len);
    }
    printf("%d\n",ans);
    return 0;
}

4. 多个字符串的最长公共子串（SAM 上匹配 + parent 树上 DP）

想同时处理所有字符串是比较困难的，我们考虑先对于一个串建立 SAM，然后对于其余的串依次求出“当匹配到状态 $state$ 时，最长的匹配长度”。

考虑对于具体某一个待匹配串 $t$，我们还是像两个字符串一样求 $t[1:i]$ 在 SAM 上匹配得到的状态以及匹配上的长度 $len$。但不同的是，我们还需要额外维护一个数组 $curlen$，表示字符串 $t$ 对于每个状态的 $\mathrm{longest}(state)$ 能匹配的最长后缀长度。更新的规则为 $curlen[x]=\mathrm{max}(curlen[x],len)$，因为 $t[1:i]$ 所对应的状态可能由多个状态转移而来，我们需要取其中最大的匹配长度。

需要注意到，我们在维护 $curlen$ 的过程中，只考虑到了 $t[1:i]$ 这不超过 $|t|$ 个状态，但实际上对于 SAM 上的任意状态均应计算 $curlen$。所以我们按照 $\mathrm{len}$ 从大到小的顺序计算没经过的状态的 $curlen$，并使用 $curlen[x]$ 来更新 $curlen[\mathrm{link}(x)]$，规则为 $curlen[\mathrm{link}(x)]=\mathrm{max}(curlen[\mathrm{link}(x)],curlen[x])$。

对于一个待匹配串 $t$ 我们能按照如上的方法求得每个状态的 $curlen$，那么所有字符串的在每个状态的最长匹配长度，就是 $ans[state]=\mathrm{min}_t(curlen_t[state])$。而最终答案为 $\mathrm{min}_{state}(ans[state])$。

例题：SPOJ-LCS2 Longest Common Substring II

#include 
#include 
#include 
using namespace std;

typedef long long ll;

const int N=100005;
const int C=26; //注意检查字符集大小！

struct SuffixAutomaton
{
    int sz,lst; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //使用nxt[clone]=nxt[q]替换memcpy
    
    SuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        lst=0;
    }
    
    void extend(int c)
    {
        int cur=++sz;
        len[cur]=len[lst]+1;
        
        int p=lst;
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                memcpy(nxt[clone],nxt[q],C*4);
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        lst=cur;
    }
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}sam;

int n,m;
char s[N],t[N];

int ans[N<<1],curlen[N<<1];

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    
    for(int i=1;i<=n;i++)
        sam.extend(s[i]-'a');
    sam.sort();
    
    for(int i=1;i<=sam.sz;i++)
        ans[i]=sam.len[i];
    
    while(~scanf("%s",t+1))
    {
        m=strlen(t+1);
        
        int cur=0,len=0;
        for(int i=1;i<=m;i++)
        {
            int p=cur,c=t[i]-'a';
            while(p!=-1 && !sam.nxt[p][c])
                p=sam.link[p],len=sam.len[p];
            
            if(p!=-1)
                cur=sam.nxt[p][c],len++;
            else
                cur=len=0;
            
            //对于同一cur，可能从多个p转移过来，故不能用len直接赋值cur
            curlen[pos]=max(curlen[pos],len);
        }
        
        for(int i=sam.sz;i>=1;i--)
        {
            int id=sam.id[i];
            curlen[sam.link[id]]=max(curlen[sam.link[id]],curlen[id]);
        }
        for(int i=1;i<=sam.sz;i++)
            ans[i]=min(ans[i],curlen[i]),curlen[i]=0;
    }
    
    int fans=0;
    for(int i=1;i<=sam.sz;i++)
        fans=max(fans,ans[i]);
    printf("%d\n",fans);
    return 0;
}

ix35 - 悲惨故事 长文警告 关于广义 SAM 的讨论）。这种现象的存在会导致进行拓扑排序等操作时出错（一个例子为 yy1695651 - ICPC2019 G题广义SAM的基排为什么不行?）。

另一方面，上述方法的复杂度与 $\sum_i |s_i|$ 线性相关，因为相当于依次插入 $n$ 个字符串。但假如题目中的字符串不是直接给出的，而是采用 trie 树的形式，那么 $n$ 个节点的 trie 树可以产生总长为 $n^2$ 级别的字符串，其形状大概如下：

出于适用范围更广的原则，本文介绍基于 trie 树和离线 bfs 的广义 SAM 实现方法。其能够建立正确的广义 SAM，同时时空复杂度仅与 trie 树的节点数相关。

洛谷P6139 【模板】广义后缀自动机（广义 SAM）

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int N=1000005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct GeneralSuffixAutomaton
{
    int sz; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(int,char)
    
    GeneralSuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        sz=0;
    }
    
    //向trie树上插入一个字符串 
    void insert(char *s,int n)
    {
        for(int i=1,cur=0;i<=n;i++)
        {
            int c=s[i]-'a';
            if(!nxt[cur][c])
                nxt[cur][c]=++sz;
            cur=nxt[cur][c];
        }
    }
    
    //扩展GSA，对于lst的c转移进行扩展 
    int extend(int lst,int c)
    {
        int cur=nxt[lst][c];
        len[cur]=len[lst]+1;
        
        int p=link[lst];
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                for(int i=0;i)
                    nxt[clone][i]=len[nxt[q][i]]?nxt[q][i]:0;
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        return cur;
    }
    
    //基于trie树建立GSA
    void build()
    {
        queue Q;
        for(int i=0;i)
            if(nxt[0][i])
                Q.push(pii(0,i));
        
        while(!Q.empty())
        {
            pii tmp=Q.front();
            Q.pop();
            
            int cur=extend(tmp.first,tmp.second);
            for(int i=0;i)
                if(nxt[cur][i])
                    Q.push(pii(cur,i));
        }
    } 
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}gsa;

int n,m;
char s[N];

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        m=strlen(s+1);
        gsa.insert(s,m);
    }
    
    gsa.build();
    
    ll ans=0;
    for(int i=1;i<=gsa.sz;i++)
        ans+=gsa.len[i]-gsa.len[gsa.link[i]];
    printf("%lld\n",ans);
    return 0;
}

出现次数也是在 parent 树上 DP。

例题：洛谷P3181 [HAOI2016]找相同字符

这道题中，具体一个状态产生的贡献是 $\left(\mathrm{len}(state)-\mathrm{minlen}(state)+1\right)\cdot cnt_1[state]\cdot cnt_2[state]$。

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int N=400005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct GeneralSuffixAutomaton
{
    int sz; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(int,char)
    
    GeneralSuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        sz=0;
    }
    
    //向trie树上插入一个字符串 
    void insert(char *s,int n)
    {
        for(int i=1,cur=0;i<=n;i++)
        {
            int c=s[i]-'a';
            if(!nxt[cur][c])
                nxt[cur][c]=++sz;
            cur=nxt[cur][c];
        }
    }
    
    //扩展GSA，对于lst的c转移进行扩展 
    int extend(int lst,int c)
    {
        int cur=nxt[lst][c];
        len[cur]=len[lst]+1;
        
        int p=link[lst];
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                for(int i=0;i)
                    nxt[clone][i]=len[nxt[q][i]]?nxt[q][i]:0;
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        return cur;
    }
    
    //基于trie树建立GSA
    void build()
    {
        queue Q;
        for(int i=0;i)
            if(nxt[0][i])
                Q.push(pii(0,i));
        
        while(!Q.empty())
        {
            pii tmp=Q.front();
            Q.pop();
            
            int cur=extend(tmp.first,tmp.second);
            for(int i=0;i)
                if(nxt[cur][i])
                    Q.push(pii(cur,i));
        }
    } 
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}gsa;

int n,m;
char s[N],t[N];
int cnt1[N<<1],cnt2[N<<1];

int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    scanf("%s",t+1);
    m=strlen(t+1);
    
    gsa.insert(s,n);
    gsa.insert(t,m);
    
    gsa.build();
    gsa.sort();
    
    for(int i=1,cur=0;i<=n;i++)
    {
        cur=gsa.nxt[cur][s[i]-'a'];
        cnt1[cur]++;
    }
    for(int i=1,cur=0;i<=m;i++)
    {
        cur=gsa.nxt[cur][t[i]-'a'];
        cnt2[cur]++;
    }
    
    ll ans=0;
    for(int i=gsa.sz;i>=1;i--)
    {
        int id=gsa.id[i];
        int lst=gsa.link[id];
        ans+=1LL*(gsa.len[id]-gsa.len[lst])*cnt1[id]*cnt2[id];
        cnt1[lst]+=cnt1[id];
        cnt2[lst]+=cnt2[id];
    }
    printf("%lld\n",ans);
    return 0;
}

多个字符串的最长公共子串也许不能用 GSA 做

SPOJ 的那题是比较弱的，因为 $n\leq 10$，所以可以存个长度为 $10$ 的数组搞一搞。以下讨论的是 $n, \sum_i |s_i|\leq 1\times 10^6$ 级别的该问题。

在 SAM 上，疑似对于每个状态暴力跳 fail 是 $\mathrm{O}(n^{1.5})$ 的。那么在 GSA 上，是否能够保证所有串各自占有的状态之和是 $|s_i|^{1.5}$ 呢？这个结论是存疑的...就算成立，时间复杂度也明显比 SAM 要差。

Kattis-firstofhername First of Her Name（2019 ICPC WF）【GSA 裸题】

题目中给定了一棵 trie 树，所以建立 GSA 是比较自然的想法。考虑回答查询，某个字符串的前缀如果是 $s$，就相当于反转的 $s$ 是从 trie 树的对应位置到 $state_0$ 的路径的前缀。所以我们只需要用类似求出现次数的方法，对于每个字符串在结尾处令 $cnt=1$（在这题中就是将 $cnt[1:n]$ 均置 $1$），然后按照拓扑序 DP 即可。

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int N=1000005;
const int C=26; //注意检查字符集大小！

ll cnt[N<<1];

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct GeneralSuffixAutomaton
{
    int sz; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(int,char)
    
    GeneralSuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        sz=0;
    }
    
    //扩展GSA，对于lst的c转移进行扩展 
    int extend(int lst,int c)
    {
        int cur=nxt[lst][c];
        len[cur]=len[lst]+1;
        
        int p=link[lst];
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                for(int i=0;i)
                    nxt[clone][i]=len[nxt[q][i]]?nxt[q][i]:0;
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        return cur;
    }
    
    //基于trie树建立GSA
    void build()
    {
        queue Q;
        for(int i=0;i)
            if(nxt[0][i])
                Q.push(pii(0,i));
        
        while(!Q.empty())
        {
            pii tmp=Q.front();
            Q.pop();
            
            int cur=extend(tmp.first,tmp.second);
            for(int i=0;i)
                if(nxt[cur][i])
                    Q.push(pii(cur,i));
        }
    } 
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            id[bucket[len[i]]--]=i;
    }
}gsa;

int n,q;
char s[N];

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        char ch=getchar();
        while(ch<'A' || ch>'Z')
            ch=getchar();
        
        int lst;
        scanf("%d",&lst);
        gsa.nxt[lst][ch-'A']=i,cnt[i]=1;
    }
    
    gsa.sz=n;
    gsa.build();
    gsa.sort();
    
    for(int i=gsa.sz;i>=1;i--)
    {
        int id=gsa.id[i];
        cnt[gsa.link[id]]+=cnt[id];
    }
    
    while(q--)
    {
        scanf("%s",s+1);
        int n=strlen(s+1);
        
        int cur=0;
        for(int i=n;i>=1;i--)
        {
            int c=s[i]-'A';
            if(!gsa.nxt[cur][c])
            {
                cur=0;
                break;
            }
            cur=gsa.nxt[cur][c];
        }
        printf("%d\n",gsa.len[cur]>=n?cnt[cur]:0);
    }
    return 0;
}

计蒜客42551 Loli, Yen-Jen, and a cool problem（2019 ICPC 徐州）【GSA 基础性质，去重处理】

这题本身挺裸的。对于每次询问 $s[x-L+1:x]$ 的出现次数，我们只需要找到其所在的状态就行了，从 $x$ 沿着 $\mathrm{link}$ 暴力跳、直到当前状态的 $\mathrm{len}$ 区间包含 $L$ 即可。理论上需要将 $x$ 相同的询问同时处理，不过数据貌似没卡。

这题稍微有点恶心的是 trie 树上会有重合的节点。对于重合的节点，我们选择最早出现的一个作为代表，其余节点全部映射到代表。这会导致非代表点变成孤立连通块，在进行拓扑排序的时候需要注意忽略这些 $\mathrm{len}=0$ 的孤立点。

#include 
#include 
#include 
#include 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int N=300005;
const int C=26; //注意检查字符集大小！

//在结构题外开任何与SAM状态相关的数组，都需要N<<1
struct GeneralSuffixAutomaton
{
    int sz; //状态数上限=2|S|-1 
    
    int len[N<<1],link[N<<1];
    int nxt[N<<1][C];
    //map nxt[N<<1];
    //extend(int,char)
    
    GeneralSuffixAutomaton()
    {
        len[0]=0,link[0]=-1;
        sz=0;
    }
    
    //扩展GSA，对于lst的c转移进行扩展 
    int extend(int lst,int c)
    {
        int cur=nxt[lst][c];
        len[cur]=len[lst]+1;
        
        int p=link[lst];
        while(p!=-1 && !nxt[p][c])
            nxt[p][c]=cur,p=link[p];
        
        if(p==-1)
            link[cur]=0;
        else
        {
            int q=nxt[p][c];
            if(len[p]+1==len[q])
                link[cur]=q;
            else
            {
                int clone=++sz;
                len[clone]=len[p]+1;
                link[clone]=link[q];
                for(int i=0;i)
                    nxt[clone][i]=len[nxt[q][i]]?nxt[q][i]:0;
                
                while(p!=-1 && nxt[p][c]==q)
                    nxt[p][c]=clone,p=link[p];
                link[q]=link[cur]=clone;
            }
        }
        return cur;
    }
    
    //基于trie树建立GSA
    void build()
    {
        queue Q;
        for(int i=0;i)
            if(nxt[0][i])
                Q.push(pii(0,i));
        
        while(!Q.empty())
        {
            pii tmp=Q.front();
            Q.pop();
            
            int cur=extend(tmp.first,tmp.second);
            for(int i=0;i)
                if(nxt[cur][i])
                    Q.push(pii(cur,i));
        }
    } 
    
    int id[N<<1];
    
    //构建完成后，id顺序为len递增（逆拓扑序）【仅可排一次】 
    void sort()
    {
        static int bucket[N<<1];
        
        memset(bucket,0,sizeof(bucket));
        for(int i=1;i<=sz;i++)
            if(len[i])
                bucket[len[i]]++;
        for(int i=1;i<=sz;i++)
            bucket[i]+=bucket[i-1];
        for(int i=1;i<=sz;i++)
            if(len[i])
                id[bucket[len[i]]--]=i;
    }
}gsa;

int n,q;
char s[N];

int to[N];
ll cnt[N<<1];

int main()
{
    scanf("%d%d",&n,&q);
    scanf("%s",s+1);
    
    gsa.nxt[0][s[1]-'A']=1,to[1]=1,cnt[1]++;
    for(int i=2;i<=n;i++)
    {
        int x,c=s[i]-'A';
        scanf("%d",&x);
        
        x=to[x];
        if(!gsa.nxt[x][c])
            gsa.nxt[x][c]=i;
        to[i]=gsa.nxt[x][c];
        cnt[to[i]]++;
    }
    
    gsa.sz=n;
    gsa.build();
    gsa.sort();
    
    for(int i=gsa.sz;i>=1;i--)
    {
        int id=gsa.id[i];
        if(id)
            cnt[gsa.link[id]]+=cnt[id];
    }
    
    while(q--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        
        x=to[x];
        while(gsa.len[gsa.link[x]]>=y)
            x=gsa.link[x];
        printf("%lld\n",cnt[x]);
    }
    return 0;
}

牛客4010D 卡拉巴什的字符串（牛客38727C Cmostp（2022 牛客暑期多校 加赛）【LCT access 维护 parent 树的链并，离线转化】

这题其实只有模型抽象用到了 SAM，所以题解写在 LCT 那里了。右端点在区间 $[l,r]$ 的状态等价于字符串 $s[1:l]$ 到 $s[1:r]$ 这 $r-l+1$ 个状态在 parent 树上的链并。

（待续）

SAM 在处理字典序相关问题时比较乏力，在这种情况下从后缀树、后缀数组的角度往往具有更好的性质。

当问题中的询问数是 $|s|$ 级别的时，可以往 SAM 想一想。

字符串

相关

js 正则匹配 两个字符串之间，某个字符串之前（之后）的内容

大爽Python入门教程 1-2 数与字符串

Java21-统计字符串中每个字符出现的次数

全（十五）Jmeter 之 参数化 函数助手：__Random string（译：瑞德.丝锥）：随机字符串

生成随机字符串

09练习：统计输入的字符串中各种字符的个数

2-14str1转义字符，格式化_2-15str2格式化，字符串内置函数

python基本数据类型；关于字符串格式化的补充

Java基础-02 字符串(汉字)与16进制字符串转换(无乱码)

C语言判断给定的字符串是否为合法的ip地址的代码-C-J

把字符串a复制到字符串b，利用指针

javascript模板字符串（反引号）

标签

一品网 冀ICP备14022925号-6