【学习笔记】后缀自动机（SAM）

前言

之前对后缀自动机的理解太浅薄了，故打算重新写一篇。

后缀自动机是什么

后缀自动机是一个字符串的所有后缀建起来的自动机。它把所有子串（后缀的前缀）用 $O(n)$ 的空间装了起来。后缀自动机的边会构成一个 $DAG$

后缀自动机的一些定义

结束位置 endpos

对于一个子串 $t$，它在原串 $s$ 里面的结束位置集合记为 $endpo{s}_t$
比如 $s=abcbc$，$t=bc$，那么 e n d p o s t = { 2 , 4 } endpos_t = \{2,4\} endpost​={2,4}（假设字符串从0开始编号）

等价类 u

所有 $endpos$ 相同子串是一个等价类，在后缀自动机上表现为一个点 $u$

后缀链接 link

其实就是我们常说的 $fail$
假设当前点为 $u$，设 $w$ 为 $endpo{s}_u$ 中最长的字符串，那么 $lin{k}_u$ 就会连向相对于 $w$ 的最长后缀的另一个 $endpos$ 上，一定会满足：
$$minle{n}_u-1=le{n}_v$$

转移 nxt

同 $trie$ 的转移，只不过所有的转移会构成一个 $DAG$

后缀自动机的一些性质

性质1

字符串 $s$ 的两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）的 $\mathrm{endpos}$ 相同，当且仅当字符串 $u$ 在 $s$ 中的每次出现，都是以 $w$ 后缀的形式存在的。

性质2

考虑两个非空子串 $u$ 和 $w$（假设 $\left|u\right|\le \left|w\right|$）。那么要么 $\mathrm{endpos}(u)\cap \mathrm{endpos}(w)=\varnothing$，要么 $\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u)$，取决于 $u$ 是否为 $w$ 的一个后缀：

$$\{\begin{array}{ll}\mathrm{endpos}(w)\subseteq \mathrm{endpos}(u)& \text{if }u\text{ is a suffix of }w\\ \mathrm{endpos}(w)\cap \mathrm{endpos}(u)=\varnothing & \text{otherwise}\end{array}$$

性质3

考虑一个 $\mathrm{endpos}$ 等价类，将类中的所有子串按长度非递增的顺序排序。每个子串都不会比它前一个子串长，与此同时每个子串也是它前一个子串的后缀。换句话说，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间 $[minlen,len]$。

性质4

所有后缀链接构成一棵根节点为 $t_0$ 的树（fail树）。

性质5

通过 $\mathrm{endpos}$ 集合构造的树（每个子节点的 $\text{subset}$ 都包含在父节点的 $\text{subset}$ 中）与通过后缀链接 $\mathrm{link}$ 构造的树相同。

性质6

对于 $t_0$ 以外的状态 $v$，可用后缀链接 $\mathrm{link}(v)$ 表达 $\mathrm{minlen}(v)$：
$$\mathrm{minlen}(v)=\mathrm{len}(\mathrm{link}(v))+1.$$

后缀自动机的构建

$SAM$ 的构建是动态的，是在线的，每次插入一个字母。
这里先声明几个定义：

• $cur$：当前节点
• $last$：上一个字母代表的节点
• $f{a}_u$：就是 $lin{k}_u$
• $nx{t}_u[c]$：后缀自动机上的边，同 $trie$ 树
• $le{n}_u$：$endpo{s}_u$ 中最长的字符串的长度。

下面是构建方法（假设当前字符为 c） ：

1. 首先我们初始化 $last=1$，即 $t_0=1$，代表初始节点（空字符串）
2. 创建一个新状态 $cur$，并令 $le{n}_{cur}=le{n}_{last}+1$ （$len$ 的定义）,此时 $f{a}_{cur}$ 无法确定，我们需要在后续的步骤确定它。
3. 令 $p=last$，如果 $nx{t}_p[c]$ 还不存在，那么就令 $nx{t}_p[c]=cur$，并让 $p$沿着 $fa$ 往上跳，即 $p=f{a}_p$，重复这个过程，直到 $nx{t}_p[c]$ 存在或者发现这样的 $p$ 不存在。
4. 如果找不到合法的 $p$，$p$ 就会跳到虚拟节点 $0$，我们令 $f{a}_{cur}=1$ 并退出。
5. 如果找到了合法的 $p$，我们记 $q=nx{t}_p[c]$
6. 如果 $le{n}_p+1=le{n}_q$，那么可以直接令 $f{a}_{cur}=q$ （$link$的性质）
7. 否则，就将当前状态 $q$ 克隆一份，记为 $r$，并将 $le{n}_r$ 赋值为 $le{n}_p+1$。复制之后，我们令 $f{a}_{cur}=r$。最后，从状态 $p$ 开始沿着 $fa$ 往上走，如果遇见 $nx{t}_p[c]=q$ 就把它改为 $r$，否则就停下来，过程结束。

struct SAM
{int fa,len;vector<int> nxt;SAM(){fa=0; len=0;nxt.assign(27,0);}
};
vector<SAM> sam;
vector<int> dp;//这里的dp求的是 endpos 集合的 size
int last;
void insert(char c)
{int ch=c-'a';sam.push_back(SAM());int cur=sam.size()-1,p;sam[cur].len=sam[last].len+1;dp.push_back(1);for(p=last; p&&sam[p].nxt[ch]==0; p=sam[p].fa){sam[p].nxt[ch]=cur;}int q=sam[p].nxt[ch];if(q==0){sam[cur].fa=1;}else if(sam[q].len==sam[p].len+1){sam[cur].fa=q;}else{sam.push_back(SAM());int r=sam.size()-1;dp.push_back(0);sam[r]=sam[q];sam[r].len=sam[p].len+1;for(; p&&sam[p].nxt[ch]==q; p=sam[p].fa) sam[p].nxt[ch]=r;sam[cur].fa=sam[q].fa=r;}last=cur;
}//sam.assign(2,SAM());
//dp.assign(2,0);
//last=1

SAM的应用

求每个点 endpos 集合的大小

根据性质2和性质5，在 $fail$ 树上，儿子是父亲的子集。所以我们可以直接在 $fail$ 树上DP。

例题：P3804 【模板】后缀自动机（SAM）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+7;
struct SAM
{int fa,len;vector<int> nxt;SAM(){fa=0; len=0;nxt.assign(27,0);}
};
vector<SAM> sam;
vector<int> dp;
int last;
void insert(char c)
{int ch=c-'a';sam.push_back(SAM());int cur=sam.size()-1,p;sam[cur].len=sam[last].len+1;dp.push_back(1);for(p=last; p&&sam[p].nxt[ch]==0; p=sam[p].fa){sam[p].nxt[ch]=cur;}int q=sam[p].nxt[ch];if(q==0){sam[cur].fa=1;}else if(sam[q].len==sam[p].len+1){sam[cur].fa=q;}else{sam.push_back(SAM());int r=sam.size()-1;dp.push_back(0);sam[r]=sam[q];sam[r].len=sam[p].len+1;for(; p&&sam[p].nxt[ch]==q; p=sam[p].fa) sam[p].nxt[ch]=r;sam[cur].fa=sam[q].fa=r;}last=cur;
}
ll ans;
vector<vector<int>> e;
void dfs(int u)
{for(auto v:e[u]){dfs(v);dp[u]+=dp[v];}if(dp[u]!=1)ans=max(ans,1ll*dp[u]*sam[u].len);
}
void O_o()
{last=1;sam.assign(2,SAM());dp.assign(2,0);string s;cin>>s;for(auto c:s) insert(c);int n=sam.size()-1;e.assign(n+1,vector<int>());for(int i=1; i<=n; i++){if(sam[i].fa){e[sam[i].fa].push_back(i);}}ans=0;dfs(1);cout<<ans;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>T;while(T--){O_o();}
}

求不同的子串个数

一开始我们就说了个性质，你在SAM上乱走就可以走出一个子串。其实只要你走的路径不同，走出的子串一定不一样。问题就变成了从 $t_0$ 出发，总共有多少条路径。这是一个经典的 DAG 上 DP 问题。转移为
$$d{p}_u=1+\sum d{p}_v$$
最后要去掉空字符串的答案，也就是 $d{p}_1-1$

如果是求子串个数，那就把 $dp$ 式子换成
$$d{p}_u=si{z}_u+\sum d{p}_v$$
其中 $si{z}_u=|endpo{s}_u|$ ，还是得减掉空字符串的方案。

void dfs2(int u)
{if(dp[u]) return ;for(int i=0; i<26; i++){int v=sam[u].nxt[i];if(!v) continue;dfs2(v);dp[u]+=dp[v];}dp[u]+=sum[u];
}

当然，求本质不同的字符串总数还有另一种方法：
根据性质3
$$ans=\sum le{n}_i-le{n}_{f{a}_i}$$

//求每次插入后有多少本质不同的字符串
void insert(int ch)
{sam.push_back(SAM());int cur=sam.size()-1,p;sam[cur].len=sam[last].len+1;dp.push_back(1);for(p=last; p&&sam[p].nxt[ch]==0; p=sam[p].fa){sam[p].nxt[ch]=cur;}int q=sam[p].nxt[ch];if(q==0){sam[cur].fa=1;}else if(sam[q].len==sam[p].len+1){sam[cur].fa=q;}else{sam.push_back(SAM());int r=sam.size()-1;dp.push_back(0);sam[r]=sam[q];sam[r].len=sam[p].len+1;for(; p&&sam[p].nxt[ch]==q; p=sam[p].fa) sam[p].nxt[ch]=r;sam[cur].fa=sam[q].fa=r;}last=cur;ans+=sam[cur].len-sam[sam[cur].fa].len;cout<<ans<<"\n";
}

求第 k 小的子串

上一个问题中我们求出了从某个节点开始走一共有多少条路径，也就是从 $i$ 开始一共有多少子串。这个时候就可以利用起来了。
如果你是在 $trie$ 树上，怎么求排名第 $k$ 的子串？——类似平衡树求第 $k$ 小。
后缀自动机也一样，只不过每个点的 $size$ 不再是 $1$ 了，而是 $endpos$ 集合大小。
只要把 trie 树上做的 $-1$ 改成 $-siz$ 即可，注意空子串还是不能算，也就是 $si{z}_1=0$。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+7,inf=1e18;
struct SAM
{int fa,len;vector<int> nxt;SAM(){fa=len=0;nxt.assign(26,0);}
};
int last=1;
vector<int> sum,dp;
vector<SAM> sam;
void insert(char c)
{int ch=c-'a';sam.push_back(SAM());int cur=sam.size()-1,p;sam[cur].len=sam[last].len+1;sum.push_back(1);for(p=last; p&&sam[p].nxt[ch]==0; p=sam[p].fa){sam[p].nxt[ch]=cur;}int q=sam[p].nxt[ch];if(!q){sam[cur].fa=1;}else if(sam[q].len==sam[p].len+1){sam[cur].fa=q;}else{sam.push_back(SAM());int r=sam.size()-1;sum.push_back(0);sam[r]=sam[q];sam[r].len=sam[p].len+1;for(; p&&sam[p].nxt[ch]==q; p=sam[p].fa){sam[p].nxt[ch]=r;}sam[q].fa=sam[cur].fa=r;}last=cur;
}
vector<vector<int>> e;
void dfs1(int u)
{for(auto v:e[u]){dfs1(v);sum[u]+=sum[v];}
}
void dfs2(int u)
{if(dp[u]) return ;for(int i=0; i<26; i++){int v=sam[u].nxt[i];if(!v) continue;dfs2(v);dp[u]+=dp[v];}dp[u]+=sum[u];
}
bool solve(int u,int k)
{k-=sum[u];if(k<=0) return 1;for(int i=0; i<26; i++){int v=sam[u].nxt[i];if(!v) continue;if(dp[v]>=k){cout<<char(i+'a');solve(v,k);return 1;}else k-=dp[v];}return 0;
}
void O_o()
{last=1;sam.assign(2,SAM());sum.assign(2,0);string s;cin>>s;for(auto c:s) insert(c);int n=sam.size()-1;dp.assign(n+1,0);int op,k;cin>>op>>k;if(op){e.assign(n+1,vector<int>());for(int i=1; i<=n; i++) if(sam[i].fa){e[sam[i].fa].push_back(i);}dfs1(1);}else{sum.assign(n+1,1);}dfs2(1);sum[1]=0;if(!solve(1,k)){cout<<"-1\n";return;}}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(12);int T=1;
//	cin>>T;while(T--){O_o();}
}

最小循环位移

循环的问题一般就是把字符串复制一遍接在后面，这个也不例外。
令 $s^{\prime }=s+s$，建立SAM
每次贪心的走最小的字符，走到长度为 $s.size()$ 时就退出。

字符串出现次数

（kmp不香吗）
先预处理每个点 $endpos$ 集合大小
然后直接拿模式串在SAM上匹配，匹配成功就是 $siz$，不成功就是 $0$