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

• 求 �π 数组

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

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

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

• 模式串匹配

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

KMP自动机

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

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

Z函数

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

• 流程

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

若 �≤�−1r≤i−1 ，则将 �l 变为 �i ，再往后推 �r。

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

注意到 �r 只加不减，时间复杂度 �(�)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 自动机

多模式串的前缀自动机。

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

• ����fail 的定义

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

流程

����trie 树的建立不说了。

����fail 的连边满足长度大小关系，所以按照长度考虑所有字符串，也就是按 ���dfs 序遍历 ����trie 树，发现 ��fa 可以由上层的 ��go 转移过来，所以可以轻松做到 �(∑∣�∣×字符集大小)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)：字典序排名为 i 的后缀的左端点。

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

ℎ(�)h(i)：排名为 i 的后缀和排名为 i-1 的后缀的 ���lcp。

流程

• 后缀排序

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

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

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

此时能得到新的 ��sa，对 ��sa 扫一遍，2�2w 相同的 ��rk 不变，否则 +1+1。

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

• 构建height

构建height有什么用？

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

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

考虑构建height。

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

这是好理解的。由此可以按下标从小到大处理，每次 −1−1 ，然后往后推。势能分析一下，时间复杂度是 �(�)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（确定性有限自动机或确定性有限状态自动机）。

后缀树

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

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

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

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

求SAM流程

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

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

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

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

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

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

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

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

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

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

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

考虑线已插入前 �−1i−1 个字符，当前插入第 �i 个字符，考虑以 �i 结尾的所有后缀。记以 �−1i−1 结尾的最后一个等价类为 ���lst，当前新插入的连通块为 ��np 且左端点属于 [1,�][1,i]。

现在考虑所有 ������endpos 包含 �−1i−1 的等价类，也就是节点 ���lst 在 ����fail 树上到根的点。

1. 对于这些等价类，若它们加上字符 ��Si​ 都转移到空状态，则将其都更新到 �p。

在不满足1的情况下，一定是节点 ���lst 先是在 ����fail 树上跳了若干个节点，后找到第一个等价类 �p 使得 ��[�][�]=�go[p][c]=q 且 �≠0q=0，�p 再往上一段同样满足指向 �q ，然后在指向其它非零节点。我们称 ��[][�]=0go[][c]=0 的这段为 �A ，��[][�]=�go[][c]=q 的这段为 �B ，�B 之上到根称之为 �C 。�A 这一段更新后一定是 ��[][�]=��go[][c]=np 的，接着要分情况讨论。

1. ���[�]+1=���[�]len[p]+1=len[q]。说明 �q 等价类一定是 ��np 等价类的后缀，可以直接有 ��[��]=�fa[np]=q，

2. ���[�]+1<���[�]len[p]+1<len[q]。首先 ���[�]+1>���[�]len[p]+1>len[q] 肯定是不成立的，否则这样的连边都是错误的。此时 �q 等价类长度 >���[�]+1>len[p]+1 的部分一定与当前的 ��np 等价类的对应部分不同，所以是不满足 �[��]=�f[np]=q。我们需要新建一个等价类 ��nq，令它对应 ���[��]=���[�]+1len[nq]=len[p]+1 的部分，[���[�]+2,���[�]][len[p]+2,len[q]] 作为新的 �q ，有 ��,�np,q 都是新等价类的儿子。其中新等价类的信息可以从 �q 继承，�B 段连向 �q 的边要改成连向新等价类的。

第三种情况可以参考下图理解。

参考代码：

void ins(int x){
	int np=++tot,p=lst;lst=np;len[np]=len[p]+1;sz[np]++;
	for(;!go[p][x];p=fa[p])go[p][x]=np;
	if(!p){fa[np]=1;return;}
	int q=go[p][x];
	if(len[q]==len[p]+1){fa[np]=q;return;}
	int nq=++tot;fa[nq]=fa[q];fa[q]=fa[np]=nq;len[nq]=len[p]+1;
	for(int i=0;i<26;i++)go[nq][i]=go[q][i];
	for(;go[p][x]==q;p=fa[p])go[p][x]=nq;
}

其他说明

• 时间复杂度 �(∣�∣×字符集大小)O(∣S∣×字符集大小)

从流程考虑，将 �A 段赋值显然是 �(�)O(n) ，所以不用考虑情况1，2。对于情况3，考虑将 �B 段改成新加等价类的复杂度。

我们记 ����depx​ 表示节点 �x 的深度，设第一个 ��[][�]go[][c] 指向 ��[��]fa[nq] 的节点为 �u ，�u 其实就是 �C 段中的第一个等价类。那么单次加的时间复杂度就是 �p 到 �u 中的节点个数，这个个数记为 �k 。

注意到，一定有 ���[��[��]]≤���[�]+1dep[fa[nq]]≤dep[u]+1

���[��]=���[��[��]]+2≤���[�]+3=���[�]−�+3=���[���]−�+3�≤���[���]+3−���[��]dep[np]=dep[fa[nq]]+2≤dep[u]+3=dep[p]−k+3=dep[lst]−k+3k≤dep[lst]+3−dep[np]

所以时间复杂度就是 ∑�∑k ,也就是 �(�)O(n) 的。

• 点数至多为2n-1

注意到每次最多加两个点，且第一二次不会复制点，这个上界是可以构造到的，����...���abbb...bbb 达到上界。

• ����fail 树为反串的后缀树

首先从未到头的插入字符，考虑从 �i 开始的一个后缀，会被分为若干个左端点在 �i 上的等价类，所有等价类的最大长度集合等于与与其他后缀的 ���lcp 大小的集合，那么建出来的后缀树与后缀数组建出来的后缀树相同。

• map替代数组