后缀自动机学习笔记

写在前面

推荐hihocoder上的讲解，可以说是十分清楚了。

用好后缀自动机不是十分容易，但看完本文的总结应该能至少达到签到水平…

正文

后缀自动机（Suffix Automaton，简称SAM）。对于一个字符串S，它对应的后缀自动机是一个最小的确定有限状态自动机（DFA），接受且只接受S的后缀。

先给出一张图和一个表格。

对于字符串STR=“aabbabd”，它的后缀自动机是：

状态	子串	endpos
S	空串	{0,1,2,3,4,5,6}
1	a	{1,2,5}
2	aa	{2}
3	aab	{3}
4	aabb,abb,bb	{4}
5	b	{3,4,6}
6	aabba,abba,bba,ba	{5}
7	aabbab,abbab,bbab,bab	{6}
8	ab	{3,6}
9	aabbabd,abbabd,bbabd,babd,abd,bd,d	{7}

接下来从状态(State)、转移函数(Transition Function)、后缀链接(Suffix Link)三个方面全方位了解一下后缀自动机的性质。

状态：

记号：

$length(s)$ 表示字符串 $s$ 的长度。
$endpos(s)$ 表示字符串 $s$ 在 $STR$ 中所有出现的结束位置集合。
$substrings(st)$ 表示状态 $st$ 中包含的所有子串的集合。
$longest(st)$ 表示状态 $st$ 包含的最长的子串， $shortest(st)$ 表示 $st$ 包含的最短的子串。
$maxlen(st)=length(longest(st))$ 。

性质:

从起始状态 $S$ 出发，沿着图中蓝线转移，对于 $STR$ 的子串最终会到达一个合法状态，不是子串的话最终会无路可走。
对于 $STR$ 的两个子串 $s_1$ 和 $s_2$ ，不妨设 $length(s_1) \leq length(s_2)$ ， $s_1$ 是 $s_2$ 的后缀当且仅当 $endpos(s_2) \subseteq endpos(s_1)$ ， $s_1$ 不是 $s_2$ 的后缀当且仅当 $endpos(s_1) \bigcap endpos(s_2) = \emptyset$
对于一个后缀自动机的状态 $st$ ， $substrings(st)$ 里的字符串 $endpos$ 集都相同，或者说同一个状态下的字符串构成了一个等价类，这样记 $endpos(st)$ 表示该状态的 $endpos$ 集。
对于一个后缀自动机的状态 $st$ ，以及任意 $s \in substrings(st)$ ，都有 $s$ 是 $longest(st)$ 的后缀。
对于一个状态 $st$ ，以及任意的 $longest(st)$ 的后缀 $s$ ，如果 $s$ 的长度满足： $length(shortest(st)) \leq length(s) \leq length(longsest(st))$ ，那么 $s \in substrings(st)$ 。
换句话说， $substrings(st)$ 包含的是 $longest(st)$ 的一系列连续后缀。

转移函数：

记字符集合 $next(st)$ 表示对于一个状态 $st$ ，从它开始下一个遇到的字符可能有哪些，形式化的写出来，有 $next(st) = {STR[i+1] \mid i \in endpos(st)}$ 。对于一个状态 $st$ 来说和一个 $next(st)$ 中的字符c，你会发现 $substrings(st)$ 中的所有子串后面接上一个字符c之后，新的子串仍然都属于同一个状态。比如对于状态4， $next(4)={a}$ ，aabb,abb,bb后面接上字符a得到aabba，abba，bba，这些子串都属于状态6。
定义转移函数 $trans(st, c) = x \mid longest(st) + c \in substrings(x)$ 。换句话说，我们在 $longest(st)$ 后面接上一个字符c得到一个新的子串 $s$ （随便哪个子串都会得到相同的结果），找到包含 $s$ 的状态 $x$ ，那么 $trans(st, c)$ 就等于 $x$ 。
对应图中蓝线，比如 $trans(4, a)=6$ 。

后缀链接：

前面我们讲到 $substrings(st)$ 包含的是 $longest(st)$ 的一系列连续后缀。这连续的后缀在某个地方会“断掉”。比如状态7，包含的子串依次是aabbab,abbab,bbab,bab。按照连续的规律下一个子串应该是“ab”，但是“ab”没在状态7里，这是因为串变短了，就有可能在别的地方也会出现，即 $endpos$ 集合大小变大了。比如aabbab,abbab,bbab,bab（状态7）的 $endpos$ 集为{6}，而“ab”（状态8）的 $endpos$ 集为{3,6}，“b”（状态5）的 $endpos$ 集为{3,4,6}。
于是我们可以发现一条状态序列：7->8->5->S。这个序列的意义是 $longest(7)$ 即aabbab的后缀依次在状态7、8、5、S中。我们用Suffix Link这一串状态链接起来，这条link就是上图中的绿色虚线。
后缀链接组成了一棵以S为根的树。

构造后缀自动机：

构造比较复杂，还是推荐看 http://hihocoder.com/contest/hiho128/problem/1

~~具体改天再写~~~

时间复杂度 $O(N)$ ，空间上状态数不超过 $2N$ 。

代码中 son 表示转移函数，pre 表示后缀链接，cnt 表示 $endpos$ 集合大小。

添加字符的过程中只能标出 $endpos$ 大小为 $1$ 的那些状态，需要对后缀链接构成的树形结构从叶子开始做拓扑排序，得到所有状态的 $endpos$ 集合大小。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
struct SAM
{
    int tot,last;
    int son[N<<1][26],maxlen[N<<1],pre[N<<1];
    int cnt[N<<1],in[N<<1],q[N<<1];
    void init()
    {
        tot=0;
        last=newnode();
    }
    int newnode()
    {
        ++tot;
        memset(son[tot],0,sizeof(son[tot]));
        maxlen[tot]=pre[tot]=cnt[tot]=in[tot]=0;
        return tot;
    }
    void add(int c)
    {
        int now=newnode();
        maxlen[now]=maxlen[last]+1;
        cnt[now]=1;
        while(last && son[last][c]==0)
            son[last][c]=now,last=pre[last];
        if(last)
        {
            int x=son[last][c];
            if(maxlen[x]==maxlen[last]+1) pre[now]=x;
            else
            {
                int nq=newnode();
                maxlen[nq]=maxlen[last]+1;
                memcpy(son[nq],son[x],sizeof(son[x]));
                pre[nq]=pre[x];
                pre[x]=pre[now]=nq;
                while(last && son[last][c]==x)
                    son[last][c]=nq,last=pre[last];
            }
        }
        else pre[now]=1;
        last=now;
    }
    void endpos()
    {
        int l=0,r=0;
        for(int i=1;i<=tot;++i) ++in[pre[i]];
        for(int i=1;i<=tot;++i)
            if(!in[i])
                q[r++]=i;
        while(l!=r)
        {
            int x=q[l++];
            if(pre[x]==0) continue;
            cnt[pre[x]]+=cnt[x];
            if((--in[pre[x]])==0)
                q[r++]=pre[x];
        }
    }
} sam;
char s[N];
int main()
{
    sam.init();
    scanf("%s",s);
    for(int i=0;s[i];++i) sam.add(s[i]-'a');
    sam.endpos();
}

广义后缀自动机

解决多个串的问题，做法很简单，只需要添加每个串前让last=1即可，或者也可以对trie树建后缀自动机，则新加点时last为trie上的父节点。分析与证明在2015年国家集训队论文里有。

如果要记录一些信息，比如strval表示每个状态里的子串在多少个串中出现过，需要额外加一个lc维护该状态上一次出现是哪个串，每次沿着Parent向上更新出现次数，遇到lc=当前串的就停止。~~时间复杂度还不太会分析，待补。~~

void add(int id,int c)//id表示第几个串，编号从1开始
{
    int now=newnode();
    maxlen[now]=maxlen[last]+1;
    cnt[now]=1;
    while(last && son[last][c]==0)
        son[last][c]=now,last=pre[last];
    if(last)
    {
        int x=son[last][c];
        if(maxlen[x]==maxlen[last]+1) pre[now]=x;
        else
        {
            int nq=newnode();
            maxlen[nq]=maxlen[last]+1;
            memcpy(son[nq],son[x],sizeof(son[x]));
            pre[nq]=pre[x];
            lc[nq]=lc[x];strval[nq]=strval[x];//额外的信息
            pre[x]=pre[now]=nq;
            while(last && son[last][c]==x)
                son[last][c]=nq,last=pre[last];
        }
    }
    else pre[now]=1;
    last=now;
    //广义后缀自动机
    while(now && lc[now]!=id)
    {
        lc[now]=id;
        ++strval[now];
        now=pre[now];
    }
}

//main

sam.init();
for(int i=1;i<=n;++i)
{
    sam.last=1;
    scanf("%s",s);
    for(int j=0;s[j];++j) sam.add(i,s[j]-'a');
}

练习题目：

1.hihocoder #1445 : 后缀自动机二·重复旋律5

求字符串本质不同子串的个数，直接累加 $\left|substrings(st) \right|$ ，利用maxlen数组及suffix link不难得出。

ll count()
{
    ll ans=0;
    for(int i=1;i<=tot;++i)
        ans+=maxlen[i]-maxlen[pre[i]];
    return ans;
}

2.spoj1811 LCS

求两个串最长公共子串，对一个串建后缀自动机，另一个串在上面走，如果当前状态没有当前字符的转移，就沿着suffix link往回跳，很好理解。

int LCS(char *s)
{
    int now=1,len=0,ans=0;
    for(int i=0;s[i];++i)
    {
        int x=s[i]-'a';
        if(son[now][x])
            ++len,now=son[now][x];
        else
        {
            while(now && son[now][x]==0) now=pre[now];
            if(now==0) len=0,now=1;
            else len=maxlen[now]+1,now=son[now][x];
        }
        ans=max(ans,len);
    }
    return ans;
}

3.[bzoj3998: TJOI2015]弦论

求一个串的第K小子串 ，T==0 表示不同位置的相同子串算作一个，T==1 则表示不同位置的相同子串算作多个。

还是先计算 $endpos$ 集合大小cnt，如果 T==0，则每个状态cnt值都是1，如果 T==1，则还是和之前的代码一样，在suffix link构成的树上做拓扑排序，转移出cnt。

另外还需要知道从每个状态往后走会有多少种子串，记为 $Sum[x]$ ，还是用同样的拓扑序转移

$Sum[x]=cnt[x]+\sum_{i=0}^{25} Sum[son[x][i]]$

然后从根开始按照字典序dfs一下就可以求出第K小子串了。

4.[bzoj3238: AHOI2013]差异

给一个字符串S，求 $\sum_{1\le i<j\le n} len(T_i)+len(T_j)-2lcp(T_i,T_j)$ ，其中 $T_i$ 表示 $i$ 开始的后缀， $lcp$ 表示最长公共前缀。

把原串倒过来建后缀自动机，这样就把前缀变成了后缀。两个前缀的最长公共后缀是对应后缀自动机上两结点的LCA ，实上统计的话，枚举LCA做类似树dp的事情数一数即可。

void addedge()
{
    for(int i=2;i<=tot;++i)
        e[pre[i]].push_back(i);
}
void dfs(int x)
{
    ll now=0;
    for(int i=0;i<e[x].size();++i)
    {
        int y=e[x][i];
        dfs(y);
        ans-=2LL*now*cnt[y]*maxlen[x];
        now+=cnt[y];
    }
    if(cnt[x]==1) ans-=2*now*maxlen[x];
    cnt[x]+=now;
}

或者这样，类似容斥一下的统计

void dfs(int x)
{
    for(int i=0;i<e[x].size();++i)
    {
        int y=e[x][i];
        dfs(y);
        cnt[x]+=cnt[y];
    }
    if(x!=1) ans-=1LL*cnt[x]*(cnt[x]-1)*(maxlen[x]-maxlen[pre[x]]);
}

5.是男人就过 8 题–Pony.AI A String Game

Alice和Bob玩游戏，有 $n$ 个串 $S_i$ ，保证都是 $t$ 的子串，每人轮流从 $n$ 个串中取出一个串，并在结尾添加一个字符后放回去，要求是添加字符之后也要保证该串是 $t$ 的子串，无法操作的人输，Alice先手，问谁赢。

显然是要在 $t$ 的后缀自动机上博弈，要注意不能直接从根开始dfs，需要先做搞出拓扑序。

int calc(char *s,int n)
{
    int now=1;
    for(int i=0;i<n;++i)
        now=son[now][s[i]-'a'];
    return ans[now];
}
void work()
{
    for(int i=1;i<=tot;++i)
        for(int j=0;j<26;++j)
            if(son[i][j])
            {
                e[son[i][j]].push_back(i);
                in[i]++;
            }
    int l=0,r=0;
    for(int i=1;i<=tot;++i)
        if(!in[i])
            q[r++]=i;
    while(l!=r)
    {
        int x=q[l++];
        int now=0;
        while(vis[x][now]) ++now;
        ans[x]=now;
        for(auto &y:e[x])
        {
            vis[y][ans[x]]=true;
            --in[y];
            if(!in[y])
                q[r++]=y;
        }
    }
}

6.bzoj1396: 识别子串

给一个串，求每个位置的最短识别子串的长度，最短识别子串定义是，在整个串中出现一次且覆盖到这个位置的最短的一个子串。

做法是找 $endpos$ 集合大小为 $1$ 的那些串，用线段树维护答案，具体是区间和一个数取min，以及和一个等差数列取min，稍微转化一下就很好写了。