前缀函数：π(i)π(i)，以 ii 结尾的最长 border 的长度。

• 求 ππ 数组

对于已经求出了前 ii 项时，是可以做到找到以 ii 结尾的所有 border。具体的，我们将 ii 向 π(i)π(i) 连边得到的树成为 fail 树，其中 ii 的 border 长度从大到小对应着 fail 树上 ii 到根链上的值。

Lemma：π(i)≤π(i−1)+1π(i)≤π(i−1)+1

对于每步，首先找到第一个匹配的 border，然后 +1+1。势能分析一下，加n次，时间复杂度 O(n)O(n)。

• 模式串匹配

先对模式串求前缀函数，匹配类似。

KMP自动机

又称前缀自动机，旨在求出 goi,cgoi,c​ ，表示在前 ii 个字符后面加一个 cc ，最长 border 的长度。

若 s(i+1)=cs(i+1)=c ，那么 goi,c=i+1goi,c​=i+1，否则goi,c=goπ(i),cgoi,c​=goπ(i),c​。

Z函数

Z函数又被称之为扩展KMP：z(i)z(i) 表示 ss 与 s[i,n]s[i,n] 的 lcplcp。

• 流程

考虑从小到大求Z函数，对于第 ii 位，前 i−1i−1 位的Z函数已经求出来了。位于区间 [l,r][l,r] 其中 r=l+z[l]−1r=l+z[l]−1 使得 rr 最大，有 l≤i−1l≤i−1。

若 r≤i−1r≤i−1 ，则将 ll 变为 ii ，再往后推 rr。

否则有 s[i,r]=s[i−l+1,r−l+1]s[i,r]=s[i−l+1,r−l+1] ，此时取 d=z(i−l+1)d=z(i−l+1)，若 i+d−1<ri+d−1<r ，那么 z(i)z(i) 直接取 dd 就是对的了。否则可以直接推 rr 。

注意到 rr 只加不减，时间复杂度 O(n)O(n)。

z[1]=m;
for(int i=2,l=1,r=1;i<=m;i++){
	if(r==i-1){
		l=r=i;
		while(b[r-l+2]==b[r+1])r++;
		z[i]=r-l+1;
		continue;
	}int d=z[i-l+1];
	if(i+d-1<r)z[i]=i+d-1;
	else{
		l=i;
		while(b[r-l+2]==b[r+1])r++;
		z[i]=r-l+1;
	}
}

AC 自动机

多模式串的前缀自动机。

大致过程分为建立 trietrie 树，求 failfail 树两个过程。求完 failfail 之后 gogo 数组就能直接按序求了，与KMP自动机是一样的。

• failfail 的定义

与KMP不同，这里的 failfail 定义为对于一个字符串 SS ，它最长的后缀使得出现在自动机中的长度。求解它的目的在于， fa[x]fa[x] 是 xx 失配后退回到的长度最大的一个状态，同理 xx 退回到的第二个状态是 fa[fa[x]]fa[fa[x]] 。可以发现将 xx 向 fa[x]fa[x] 连边可以得到一棵树，这棵树称之为 failfail 树，且 xx 失配后的所有退回状态都在从 xx 到根的链上，且深度越深长度越大。

流程

trietrie 树的建立不说了。

failfail 的连边满足长度大小关系，所以按照长度考虑所有字符串，也就是按 dfsdfs 序遍历 trietrie 树，发现 fafa 可以由上层的 gogo 转移过来，所以可以轻松做到 O(∑∣S∣×字符集大小)O(∑∣S∣×字符集大小)。

代码

struct AC_automaton{
	int go[M][C],ba[M],fa[M],np,id[M],q[M],he,ta,cnt,dfn[M],sz[M];
	void ins(char ch){
		int c=ch-'a';
		if(go[now][c])now=go[now][c];
		else go[now][c]=++np,ba[np]=now,g[now].emplace_back(np),now=np;
	}
	void build(){he=1;ta=0;
		for(int i=0;i<C;i++)if(go[0][i])q[++ta]=go[0][i];
		while(he<=ta){
			int u=q[he++];e[fa[u]].emplace_back(u);
			for(int i=0;i<C;i++){
				if(go[u][i])fa[go[u][i]]=go[fa[u]][i],q[++ta]=go[u][i];
				else go[u][i]=go[fa[u]][i];
			}
		}
	}
}

SA

sa(i)sa(i)：字典序排名为 i 的后缀的左端点。

rk(i)rk(i)：后缀 s[i,∣s∣]s[i,∣s∣] 的排名。sa(rk(i))=rk(sa(i))=isa(rk(i))=rk(sa(i))=i。

h(i)h(i)：排名为 i 的后缀和排名为 i-1 的后缀的 lcplcp。

流程

• 后缀排序

对长度 ww 倍增，每次完成从 ww 的状态转移到 2w2w。

本质上是双关键字排序，先按前 ww 排，在按后 ww 排。

代码实现上，先确定前 ww 相同所形成的若干段，对所有下标按后 ww 排序，然后倒序插入预留的段中。

此时能得到新的 sasa，对 sasa 扫一遍，2w2w 相同的 rkrk 不变，否则 +1+1。

由于字符串后缀都不相同，所以当 rkrk 到 nn 时退出即可。时间复杂度 O(nlogn)O(nlogn) 。

• 构建height

构建height有什么用？

Lemma：对于排名i与排名j的后缀 (i<j)(i<j)，它们的 lcplcp 等于 mink=ij−1hkmink=ij−1​hk​。

proof：对于其中任意相邻两项 k,k+1k,k+1 ，对于超出 h(k)h(k) 的部分，k+1k+1 的字典序一定比 kk 的大，那么对于大于 k+1k+1 的一个 pp ，若 pp 的前 h(k)h(k) 部分相同，一定有后面部分字典序比 kk 大，所以 ii 与 jj 的 lcplcp ，一定是由其中相邻最小的 lcplcp 决定的。

考虑构建height。

Lemma：h(rk(i))≥h(rk(i−1))−1h(rk(i))≥h(rk(i−1))−1

这是好理解的。由此可以按下标从小到大处理，每次 −1−1 ，然后往后推。势能分析一下，时间复杂度是 O(n)O(n) 的。

代码

void SA(){
	m=128;
	for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=1;i<=n;i++)sa[cnt[rk[i]]--]=i;
	for(int w=1;;w<<=1,m=p){
		memset(cnt+1,0,m<<2);
		for(int i=n-w+1;i<=n;i++)id[++cur]=i;
		for(int i=1;i<=n;i++){cnt[rk[i]]++;if(sa[i]>w)id[++cur]=sa[i]-w;}
		for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		swap(old,rk);p=0;
		for(int i=1;i<=n;i++){
			if(old[sa[i]]==old[sa[i-1]]&&old[sa[i]+w]==old[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}if(n==p)break;
	}
	for(int i=1,k=0;i<=n;i++){
		if(rk[i]==1)continue;
		if(k)k--;
		while(s[i+k]==s[sa[rk[i]-1]+k])k++;
		h[rk[i]]=k;
	}
}

SAM

后缀自动机。能够接受模式串的所有子串最简状态自动机，也是接受所有后缀的最小DFA（确定性有限自动机或确定性有限状态自动机）。

后缀树

我们知道多模式串的前缀树就是 trietrie ，且由于前缀共用的特点，节点的个数是 O(∑∣S∣)O(∑∣S∣) 的。如果用类似的方式建后缀树，把串的每个后缀都插入 trietrie 中，得到的树形结构就满足存在所有子串的性质，但是这样的节点数是 O(∣S∣2)O(∣S∣2) 的。

考虑如何缩减状态。将所有后缀的终节点或是儿子数大于1的节点保留，其余的边浓缩，如此得到的树的节点是 2n−12n−1 的。实际上，这样操作得到的树就是以所有后缀终节点生成的虚树。

可以发现，模式串的子串不一定都在节点上，有可能在边上，但一种子串一定只会有一种映射，根据这个特点，建好后缀树之后，就能知道本质不同子串个数。

从后缀数组的角度理解后缀树。对于后缀节点按后缀树上的dfs序排序得到的就是 sasa 数组，这是好理解的。按 hh 生成的笛卡尔树就是后缀树（注意删掉空字符的边），分治证明也是容易的。通过求SA的方式已经可以建后缀树，但与SAM相比，它不支持在末尾动态的插入字符。

求SAM流程

主体思路是增量构造，也就是支持在末尾加点的同时，对后缀DFA的动态维护。

根据前面的经验，要维护DFA就需要维护 failfail 数组，需要动态的维护后缀树的结构，大概需要实现加点/分裂/合并等操作。

引入一个概念：endposendpos 集合，称 endpos(T)endpos(T) 表示子串 TT 在模式串中所有终位置构成的下标集合。我们称 endposendpos 集合相同的点处于同一个等价类中。

Lemma1：同一个等价类的字符串，一定成后缀关系。

Lemma2：endposendpos 集合只存在包含与不交关系，不存在交叉关系，形成树形结构。

Lemma3：模式串所有子串的本质不同等价类个数是 O(n)O(n) 的。
proof：考虑反串的后缀树，一条排开起点包含终点的一条边，其中所有包括浓缩的节点对应的串是一个等价类，这是容易发现的，所以等价类的个数就与后缀树节点个数同样是 O(n)O(n) 的。

看到Lemma3的证明你也许会思考既然是反串的后缀树，为什么不能改成原串的后缀树，在把 endposendpos 变成 startposstartpos 呢?其实是由于每次的加字符是在字符串的末尾执行的，所以对于 endposendpos 的改变是容易维护的，但 startposstartpos 就不一定了，这也导致后面将说的SAM建出来的fail树是反串的后缀树。

再做一些定义，比如对于某个左端点属于 [l,r][l,r] 右端点可以为 pp 的等价类 xx（ pp 为等价类 xx 的 endposendpos 集合中的一点），令 len[x]=p−l+1len[x]=p−l+1 。

fa[x]fa[x] 表示的是 pp 相同的条件下的上一个等价类，有len[fa[x]]=p−rlen[fa[x]]=p−r。

go[x][c]go[x][c] 表示在等价类 xx 的后面插入字符 cc 之后得到的等价类。

动态的维护上述值的过程就是SAM算法的核心。