标签：nxt 后缀 int 知识 整理 maxn 字符串 link sim

引入：字符串最长公共前缀（Longest Common Prefix，LCP）

普通求法

利用 hash。设需要求 \(S,T\) 字符串的 LCP，则可以二分长度 \(len\)，求一个最大的 \(len\) 满足 \(hash(S_1\sim S_{len})=hash(T_1,T_{len})\)。

---

后缀数组（Suffix Array,SA）

例题1：

给出长为 \(n\) 的字符串 \(S\)，求最长的子串 \(A\)，使得 \(A\) 在 \(S\) 中可重复地出现了两次。

核心做法

定义 \(s_i=S_{i\sim n}\)，则原题等效于求 \(\max_{i,j\in[1,n],i\ne j}|LCP(s_i,s_j)|\)。

数据范围1：\(n\le 10^3\)。

直接 \(O(n)\) 或 \(O(n^2)\) 处理所有 \(s\) 的所有后缀的 hash 值，然后 \(O(n^2\log n)\) 暴力枚举所有的 \(i,j\)，二分出对应的 \(|LCP(s_i,s_j)|\)。

数据范围2：\(n\le 10^5\)。

考虑固定 \(i\)，求 \(\max_{j=1}^n|LCP(s_i,s_j)|\)。可以把所有的 \(s\) 按照字典序进行排序，然后某个 \(i\) 对应的 \(j\) 一定在排好序的所有 \(s\) 中 \(s_i\) 的前/后一个之间。故而可以使用二分 + hash 比较任意两个 \(s\) 的字典序大小和 LCP 长度，使用快速排序，时间复杂度为 \(O(n\log^2n)\)。

数据范围3：\(n\le 10^6\)。

此时我们需要一种更快速的方法对所有后缀进行排序+处理 LCP 长度。

发现如果已经知道 \(s_i\) 和 \(s_j\) 的前半部分和后半部分的字典序大小关系，则可以在 \(O(1)\) 的时间内求出 \(s_i\) 和 \(s_j\) 的大小关系。

可以使用倍增排序。设 \(rnk_{j,i}\) 表示只取每个 \(s\) 的前 \(2^j\) 位进行比较后 \(s_i\) 的排名。考虑如何由 \(rnk_{j,i}\) 推到 \(rnk_{j+1,i}\)。任意两个后缀 \(s_a\) 和 \(s_b\) 的前 \(2^j\) 位的字典序大小可以直接在 \(rnk_j\) 中得出，而后 \(2^j\) 位的字典序大小关系就是 \(rnk_{j,a+2^j}\) 和 \(rnk_{j,b+2^j}\) 的大小关系。由此我们推出了 \(rnk_{j+1}\)，在 \(O(\log n)\) 次这样的过程后即可求所有 \(s\) 的真正大小关系。

使用快速排序的单次处理的时间复杂度是 \(O(n\log n)\)。由于单次处理实质是双关键字排序，而这两个关键字的值域均为 \(O(n)\)，可以使用基数排序（\(O(\log n)\) 次操作的总复杂度为 \(O(n\log n)\)），给出一种使用链表实现的代码：

后缀数组模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
const int maxb=2620010;
int n,i,j,k,d=1,r,b=1,m,p;
int h1[maxn],n1[maxn],h2[maxn],n2[maxn];
int rnk[maxb],nrk[maxn],pla[maxn];
int main(){
	for(n=1;;++n){
    	rnk[n]=getchar();m=max(m,rnk[n]);
    	if(rnk[n]=='\n'||rnk[n]<0) break;
	}
	rnk[n--]=0;
	p=n; while(p>>=1) ++b;
	for(i=1;i<=b;++i,d<<=1){
		for(j=1;j<=n;++j){
			n2[j]=h2[rnk[j+d]];
			h2[rnk[j+d]]=j;
		}
		for(j=0;j<=m;++j){
			for(k=h2[j];k;k=n2[k]){
				n1[k]=h1[rnk[k]];
				h1[rnk[k]]=k;
			}
		}
		p=n;
		for(j=m;j>=0;--j) for(k=h1[j];k;k=n1[k]) pla[p--]=k;
		for(j=0;j<=m;++j) h1[j]=n1[j]=h2[j]=n2[j]=0;
		r=nrk[pla[1]]=1;
		for(j=2;j<=n;++j){
			if(rnk[pla[j-1]]<rnk[pla[j]]||
			   rnk[pla[j-1]+d]<rnk[pla[j]+d]) ++r;
			nrk[pla[j]]=r;
		}
		m=0;
		for(j=1;j<=n;++j){
			rnk[j]=nrk[j];
			m=max(rnk[j],m);
		}
	}
	for(i=1;i<=n;++i) printf("%d ",pla[i]);
	return 0;
}

求出每个后缀的字典序的排名后（\(s_i\) 的排名记为 \(r_i\)），考虑就此使用另一种方式（而不是基于 hash 的 \(O(n\log^2n)\) 的做法）求 LCP。

---

Height 数组

定义

\(h_i\) 为满足 \(s_a=i\) 和 \(s_b=i-1\) 的 \(|LCP(s_a,s_b)|\)（\(h_1\) 为 \(0\)，假设 \(s_0\) 为空串）

引理

\(\forall i>1,h_{r_i}\ge h_{r_{i-1}}-1\)。

证明

反证法。若对于 \(s_{i-1}\) 存在一个 \(j\) 满足 \(|LCP(s_j,s_{i-1})|>h_{r_i}+1\) 且 \(r_j<r_{i-1}\)，则去掉 \(LCP(s_j,s_{i-1})\) 的第一个字符即可得到 \(LCP(s_{j+1},s_i)\)，必有 \(|LCP(s_{j+1},s_i)|>h_{r_i}\)。而由定义得 \(h_{r_i}=\max_{s_j<s_i}|LCP(s_j,s_i)|\)（设对所有后缀排好序后 \(s_i\) 的前一个后缀为 \(s_{p_i}\)，若 \(\exists j,s_j<s_i,|LCP(s_j,s_i)|>|LCP(s_{p_i},s_i)|\)，则 \(S_{j+|LCP(s_{p_i},s_i)|}=S_{i+|LCP(s_{p_i},s_i)|}\) 且 \(S_j\sim S_{j+|LCP(s_{p_i},s_i)|-1}=S_i\sim S_{i+|LCP(s_{p_i},s_i)|-1}\)，而 \(S_{j+|LCP(s_{p_i},s_i)|}<S_{i+|LCP(s_{p_i},s_i)|}\)，故而一定有 \(s_j>s_{p_i}\)，与 \(p_i\) 的定义矛盾），且由 \(s_{j_1}=s_{{i-1}_{1}}\) 必有 \(r_{j+1}<r_i\)；与 \(h\) 的定义矛盾。故而 \(\forall i>1,h_{r_i}\ge h_{r_{i-1}}-1\)。

---

于是可以令 \(p=h_{r_{i-1}}\)，在计算 \(h_{r_i}\) 时直接从 \(S_{i+p-1}\) 开始匹配，将 \(p\) 不断自增直到 \(S_{i+p}\) 为最后一个相等的字符为止，此时必有 \(p=h_{r_i}\)。由于 \(\max h\le n\) 且 \(h_{r_i}\ge h_{r_{i-1}}-1\)，则匹配的总时间复杂度是 \(O(n)\) 的。这样也就求出了此题的答案。

后缀数组的定义

后缀数组主要包含两个数组：\(sa\) 和 \(rk\)。

\(sa_i\) 是字符串的所有后缀按照字典序升序排序后第 \(i\) 个后缀对应的下标，\(rk_i\) 为这个字符串的第 \(i\) 位开始的后缀的排名。

求两子串的 LCP

对于两个字符串 \(S\) 和 \(T\)，以及一个字典序在它们中间的字符串 \(s\)，一定有 \(|LCP(S,T)|=\min(|LCP(S,s)|,|LCP(s,T)|)\)（显然 \(S\) 和 \(T\) 和 \(s\) 的前 \(|LCP(S,T)|\) 位是一样的，而 \(S\) 和 \(T\) 的第 \(|LCP(S,T)|+1\) 位不一样，\(s\) 的这一位只能和 \(S\) 和 \(T\) 的这一位之一相同）。

故而有 \(|LCP(s_i,s_j)|=\min_{k=rk_i}^{rk_j} h_k(rk_i<rk_j)\)。求任意两个后缀的 LCP 即转化成了 RMQ 问题。

例题2

给出长为 \(n\) 的字符串 \(S\)，求最长的子串 \(A\)，使得 \(A\) 在 \(S\) 中不可重复地出现了两次。\(n\le 10^6\)。

解法

求出后缀数组和 height 数组。二分答案的长度 \(k\)，然后求 \(k\) 是否合法等效于在 \(h\) 中是否存在一段连续段满足最小值不小于 \(k\) 且 \(sa\) 对应的一段极差大于 \(k\)。可以使用笛卡尔树或并查集处理。

例题3

给出长为 \(n\) 的字符串 \(s\)，求其第 \(k\) 小子串。需要给出重复计数和不重复计数的两种答案。\(k\le 10^9\)。

数据范围0：\(n\le 5\times 10^5\)。

数据范围1：\(n\le 10^6\)。

考虑后缀数组的性质。求出 \(sa\) 后，发现所有的 \(sa_i\) 的 \(n-sa_i+1\) 个前缀刚好对应了原串中的所有子串。

考虑不重复计数的情况，显然第 \(sa_i\) 个后缀的前缀中有 \(h_i\) 个是和第 \(sa_{i-1}\) 个的前缀相同；而 \(S_i\sim S_{i+h_i}\) 到 \(S_i\sim S_n\) 字典序递增；并且最后一个个前缀 \(T=S_i\sim S_n\) 的字典序一定比 \(sa_1\sim sa_{i-1}\) 的任何一个前缀都要大，比 \(sa_{i+1}\sim sa_n\) 的任何一个不与上一个后缀重复前缀都要小。综上，第 \(sa_i\) 后缀一定贡献了 \(n-i-h_i+1\) 个子串，且所有的子串已按照字典序升序排好。

而对于重复计数的情况，考虑有某个前缀的字符串有多少种。若某个前缀长为 \(k\)，且以此为前缀的原串后缀的字典序最小者为 \(s_p\)，则满足 \(h_i<k,i\ge p\) 的最小 \(i\) 对应的 \(s_p\sim s_i\) 均以这个长为 \(k\) 的前缀为前缀，以其为前缀的所有子串数即为 \(\sum_{j=p}^i (n-j-k+1)\)。故而按位得出答案的前缀直至其后再不能加字符即可。

例题4

给出长为 \(n\) 的字符串 \(s\)，对于其子串 \(a\)，设 \(a\) 在 \(s\) 中出现了 \(k\) 次，求 \(\max k|a|[k>1]\)。

数据范围1：\(n\le 10^3\)。

可以对于每个长度，将 \(s\) 扫一遍，至于维护目前扫到的字符串出现了多少次，可以使用 hash + 桶存放某种字符串被扫到了多少次。时间复杂度是 \(O(n^2)\) 的。

数据范围2：\(n\le 10^6\)。

考虑后缀数组。由于每个子串均可以看作 \(s\) 的某个后缀的前缀，故而固定 \(a\) 的一个长度 \(k\) 时，若区间 \([l,r]\) 满足 \(\min_{i=l}^r h_i\ge k\)，则 \(sa_{l-1}\sim sa_r\) 后缀均有相同的长为 \(k\) 的前缀。同样可以使用笛卡尔树或并查集解决。其中并查集的做法是将 \([1,n]\) 中每个数事先划到一个连通块中，然后从大到小枚举长度，当枚举到 \(k\) 时，对于 \(\forall h_i=k+1\)，将 \(i-1\) 和 \(i\) 所在的连通块合并，然后查询此时最大连通块的大小（记为 \(siz_k\)），\(\max siz_kk\) 即为答案。

亲测没怎么卡常的 SA 做法能过。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
const int maxb=2620010;
int n,i,j,k,d=1,r,b=1,m,p;
long long ans;
char s[maxn];
int h1[maxn],n1[maxn],h2[maxn],n2[maxn];
int rnk[maxb],nrk[maxn],pla[maxn];
int fa[maxn],ht[maxn],siz[maxn];
int Find(const int &p){
	if(p==fa[p]) return p;
	return fa[p]=Find(fa[p]);
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(i=1;i<=n;++i){
    	rnk[i]=s[i];
		m=max(m,rnk[i]);
		fa[i]=i;siz[i]=1;
	}
	p=n;
	while(p>>=1) ++b;
	for(i=1;i<=b;++i,d<<=1){
		for(j=1;j<=n;++j){
			n2[j]=h2[rnk[j+d]];
			h2[rnk[j+d]]=j;
		}
		for(j=0;j<=m;++j){
			for(k=h2[j];k;k=n2[k]){
				n1[k]=h1[rnk[k]];
				h1[rnk[k]]=k;
			}
		}
		p=n;
		for(j=m;j>=0;--j) for(k=h1[j];k;k=n1[k]) pla[p--]=k;
		for(j=0;j<=m;++j) h1[j]=n1[j]=h2[j]=n2[j]=0;
		r=nrk[pla[1]]=1;
		for(j=2;j<=n;++j){
			if(rnk[pla[j-1]]<rnk[pla[j]]||
			   rnk[pla[j-1]+d]<rnk[pla[j]+d]) ++r;
			nrk[pla[j]]=r;
		}
		m=0;
		for(j=1;j<=n;++j){
			rnk[j]=nrk[j];
			m=max(m,rnk[j]);
		}
	}
	j=m=0;
	for(i=1;i<=n;++i){
		if(!rnk[i]) continue; if(j) --j;
		while(s[i+j]==s[pla[rnk[i]-1]+j]) ++j; 
		ht[rnk[i]]=j;n1[rnk[i]]=h1[j];h1[j]=rnk[i];
		m=max(m,j);
	}
	j=1;
	for(i=m;i;--i){
		for(k=h1[i];k;k=n1[k]){
			b=Find(k-1);r=Find(k);
			j=max(j,siz[b]+=siz[r]);
			fa[r]=b;
		}
		if(j==1) continue;
		ans=max(1LL*i*j,ans);
	}
	printf("%lld",ans);
	return 0;
}

数据范围3：\(n\le 10^7\)。

求后缀数组是有 \(O(n)\) 的 SA-IS 和 DC3 算法的。

但是我们的重点不在于此，而是介绍一种名为 后缀自动机 的科技。

---

后缀自动机（Suffix AutoMaton,SAM）

---

引入：自动机

下述讨论的自动机为 确定有限状态自动机（DFA）。

自动机是一种能够接收（由边权组成的）路径的有向图，有边权，起点（下面记为 \(t_0\)）和终点（可能有若干个）。对于一条路径，若能顺着路径上的每一种对应的边权由起点走到某个终点，则称其能接受这条路径。显然从起点出发的每条路径对应的边权序列唯一。

---

定义

后缀自动机能且只能接受某个字符串的若干后缀。在所有构造出来的满足这个功能的自动机中，SAM 的节点是最少的。

性质

SAM 的每条边上均对应一个字符，由于从起点到某个终点的路径对应一个后缀，因此从起点出发的每条路径的每条路径均对应了一个子串。同时由于 SAM 的一个点可能会由多条路径到达，因此每个点对应了这些子串的集合。

相关概念

1. endpos

对于 \(s\) 的非空子串 \(t\)，记 \(endpos(t)\) 为 \(t\) 在 \(s\) 中的所有结束位置的集合。特别地，\(endpos({\texttt{空串}})=\{0,1,2,\cdots,n\}\)。

同时若两个串的 endpos 集合相同，则称这两个串为 endpos 等价的。由于这个关系满足自反性、对称性和传递性等性质，则 \(s\) 的所有子串可以被划分为若干个 endpos 等价类。而 SAM 的起点之外的每个节点即代表一个 endpos 等价类。

endpos 的一些性质：

1. 对于子串 \(s\) 和 \(t\)（\(|s|\le|t|\)，下同），若 \(s\) 与 \(t\) endpos 等价，则必有 \(s\) 是 \(t\) 的后缀，反之则不一定。证明显然。

2. 若 \(s\) 不是 \(t\) 的后缀，则 \(endpos(s)\cap endpos(t)=\emptyset\)，否则 \(endpos(t)\subseteq endpos(s)\)。证明同样显然。

3. 将一个 endpos 等价类中的字符串按字典序从小到大排序，则每个字符串均是后一个字符串移除第一个字符得来的。

   证明：

   若这个 endpos 等价类只包含一个字符串，则显然成立。

   若这个 endpos 等价类包含不止一个字符串，考虑其中最长的字符串 \(s\) 和最短的字符串 \(t\)。显然 \(t\) 是 \(s\) 的后缀，考虑 \(s\) 的任意一个比 \(t\) 长的后缀 \(p\)。由于 \(endpos(t)\subseteq endpos(p)\subseteq endpos(s)\) 且 \(endpos(t)=endpos(s)\)，故而 \(endpos(t)=endpos(p)=endpos(s)\)，\(p\) 一定在这个 endpos 等价类中。

2. 后缀链接 link

由前述内容可知：对于某个作为其所在 endpos 等价类中最长的字符串 \(s\)，不断将其第一个字符移除，则在某次这样操作之后其一定会变成处于另一个等价类的字符串 \(t\)（其中 \(t\) 可能是空串，而空串不与任意非空串等价），则定义 \(link(endpos(s))=endpos(t)\)，具体为从 \(endpos(s)\) 连向 \(endpos(t)\) 的有向边。

显然在不断删去 \(s\) 的最前面的字符之后，\(s\) 会变成空串，也就是 \(t_0\) 代表的状态（从 \(t_0\) 到 \(t_0\) 的简单路径为空），故而所有 \(link\) 构成的有向图形态是以 \(t_0\) 为根的内向树。

同时若 \(link(s)=t\)，一定有 \(s\subsetneq t\)，子节点代表的 endpos 一定包含于父亲节点代表的 endpos 中，且两个无祖先后代关系的节点对应的 endpos 集合交集一定为空（它们代表的字符串无后缀关系）。故而最后后缀链接构成的树本质上是 endpos 集合构成的树。特别地，如果从代表整个串的节点开始，不断走 \(link\) 边直到 \(t_0\) 节点，则走到过的节点对应的所有字符串一定是整个串的所有后缀，也就是说这些节点即是自动机上的终点。

构造

定义 \(longest(v)\) 表示 \(v\) 节点对应的最长子串，\(len(v)\) 表示 \(longest(v)\) 的长度，\(min(v)\) 表示 \(v\) 节点对应的最短子串，\(minlen(v)\) 表示 \(v\) 节点对应的最短子串的长度。显然有 \(minlen(v)=len(link(v))+1\)。

构造 SAM 时我们采用在线算法“增量法”，每一次在字符串末尾插入一个字符。同时在 SAM 的每个节点上只保存其 \(len\)、\(link\) 和对应的转移列表，而不标记终止状态（以保证空间复杂度）。

考虑在目前已有的字符串后插入字符 \(c\) 时的做法。令 \(last\) 为目前整个字符串对应的节点（一开始 \(last\) 为 \(1\)）。

在插入 \(c\) 时，先创造一个状态 \(cur\)，将 \(len(cur)\) 设为 \(len(last)+1\)（此时未确定 \(link(cur)\)）。然后从 \(last\) 开始，如果还没有到字符 \(c\) 的转移，则添加一个到 \(c\) 的转移，然后将 \(last\) 赋为 \(link(last)\)，否则令此时的 \(last\) 为 \(p\) 并停止此过程。如果最后都没有找到 \(p\)，则直接把 \(link(cur)\) 赋为 \(1\) 并退出。否则记 \(son(p,c)=q\)。

分类讨论 \(q\) 与 \(p\) 的关系。若 \(len(q)=len(p)+1\)，则只需要把 \(link(cur)\) 赋值为 \(q\)。否则需要 复制 状态 \(q\)：新建一个 \(clone\) 状态，复制 \(q\) 的 \(link\) 和转移，将 \(len(clone)\) 赋为 \(len(p)+1\)。复制之后，将 \(link(cur)\) 和 \(link(q)\) 均赋为 \(clone\)。然后，若 \(p\) 或 \(p\) 的后缀链接树上的祖先存在到 \(q\) 的转移，则将该转移重定向到 \(clone\)。

最后把 \(last\) 更新为 \(cur\)。

理解

考虑 SAM 上的转移代表在某个字符串最后加上某个字符。显然在字符串结尾加上字符 \(c\) 只会对目前所有的后缀造成影响。在加入某个字符 \(c\) 后，首先要创建一个新的等价类 \(cur\)，然后将所有后缀加上 \(c\)。对于原来的串 \(S\)，需要把其后缀加上 \(c\) 时，需要从 \(last\) 开始找到所有的后缀对应的所有节点。理论上我们需要将所有后缀对应节点均检查有无 \(c\) 的转移（无则加上），但如果某个节点对应有 \(c\) 的转移，则其 \(link\) 到的节点肯定也有 \(c\) 的转移（存在这样的字符串）；故而从这个节点开始即不必再跳 \(link\)。反之，如果跳到了 \(t_0\) 还是没有找到 \(c\) 的转移，则字符 \(c\) 未出现在串中，\(S+c\) 的所有后缀一定只对应了一个等价类。

考虑找到 \(c\) 的转移（存在上述的 \(p\) 和 \(q\)）之后该如何做。由于 \(longest(link(cur))=longest(p)+c\)（\(longest(p)\) 刚好是 \(S\) 的最长的满足后面有 \(c\) 的前缀，而更长的前缀没有 \(c\) 的转移），故而若 \(len(q)=len(p)+1\) 则 \(link(cur)=q\)。否则，由于 \(longest(p)+c\) 的等价类由 \(q\) 变成了 \(q\cup \{|S|+1\}\)，故而要新建一个状态 \(clone\)，把 \(longest(p)+c\) 独立出来。同时需要把 \(link(cur)\) 和 \(link(q)\) 均赋为 \(clone\)。而 \(clone\) 后面能加的字符与 \(q\) 一致，\(min(q)\) 和 \(min(clone)\) 相同，显然 \(q\) 的转移边和 \(link\) 要复制给 \(clone\)。同时 \(longest(clone)\) 可以在前面加一个字符变成等价类仍为先前 \(q\) 对应的等价类的字符串，故而需要将 \(link(q)\) 设为 \(clone\)。最后对于 \(p\) 及其在 \(link\) 树上的祖先先前指向 \(q\) 的转移边重定向到 \(clone\) 显然是因为 \(min(clone)=min(q)\)。

有一个优化：考虑 \(p\) 在后缀链接树的某个祖先 \(b\) 对应的 \(c\) 转移边没有连接到 \(q\)，则 \(b\) 及其对应的祖先 \(x\) 对应的 \(|longest(x)-c|\) 一定小于 \(minlen(q)\)，故而 \(x\) 的 \(c\) 转移边一定不会连到 \(q\)。这会是时间复杂度优化的重要依据之一。

时间复杂度证明

下面我们令目前操作中转移边的查找、修改、增加等操作均为单次 \(O(1)\) 的（如果字符集很大或者字符集不确定，则需要用到 std::map，转移边相关的操作会是单次 \(O(\log\Sigma)\) 的，其中 \(\Sigma\) 是字符集大小）。

节点数

SAM 在每次添加字符后最多只会增加两个节点，故而其节点数（状态数）不超过 \(2n-1\)。有且只有 \(abb\cdots b\) 可以达到这个上界，由于在每次添加字符后找到的 \(p,q\) 均不满足 \(len(q)=len(p)+1\)。

转移数

定义一个转移 \(p\rightarrow q\) 为连续的当且仅当 \(len(q)=len(p)+1\)，反之则不连续。显然两个点之间的最长路径一定只有连续的转移。

对于连续的转移，考虑 SAM 中以 \(t_0\) 为根的所有最长路径的生成树。由于生成树只包含连续的边，故而这些边的数量少于节点数，不会超过 \(2n-2\) 条。

令一个不连续的转移为 \(p\stackrel c\rightarrow q\)，且 \(u\) 为从 \(t_0\) 到 \(p\) 对应的最长路径，\(w\) 为从 \(q\) 到任意一个终止状态对应的路径。（由于 \(u+c\) 对应了某个子串，从这个子串一定能延伸成一个后缀，故而 \(w\) 一定存在）则 \(u+c+w\) 一定是原串的一个后缀，且 \(t_0\rightarrow p\stackrel c\rightarrow q\rightarrow {\footnotesize\texttt{这个终止状态}}\) 显然是从 \(t_0\) 出发唯一的表示 \(u+c+w\) 的路径。同时由于原串是 \(longest(last)\)，故而 \(u+c+w\) 一定不会代表原串。故而最后不连续转移的数量不超过 \(n-1\)。

最后所有转移数不会超过 \(3n-3\)（更确切地说是 \(3n-4\)，由于状态数为 \(2n-1\) 的情况 \(abb\cdots b\) 转移数只为 \(2n-1\)，而 \(abb\cdots bc\) 可以达到 \(3n-4\) 的上界）

操作数

考虑一下不能直接看出总时间复杂度为 \(O(n)\) 的操作：

• 遍历 \(last\) 在后缀链接树上的祖先并添加转移。
• 将 \(q\) 的状态复制给 \(clone\) 并复制转移。

由于 SAM 上的点数和边数均为 \(O(n)\) 的，故而这两种操作的总时间复杂度是 \(O(n)\) 的。

• 将指向 \(q\) 的转移重定向到 \(clone\)。

考虑 \(minlen(link(last))\) 的变化。设 \(p\) 在后缀链接树的最远的满足需要与 \(clone\) 连接的祖先为 \(d\)，则显然有 \(minlen(link(last))\ge minlen(p)\ge minlen(d)\)，故而 \(minlen(link(cur))=minlen(clone)=minlen(d)+1\)。如果 \(d\) 为 \(p\) 的 \(k\) 级祖先（跳了 \(k\) 次），由于每跳一级 \(link\)，\(minlen\) 一定会减少，故而 \(minlen(d)\le minlen(p)-k\le minlen(link(last))-k\)，\(minlen(link(cur))\le minlen(link(last))-k+1\)。也就是说 \(minlen(link(last))\) 在每次操作后均会增加不超过 \(1\)，而在这个操作上找了 \(p\) 的 \(k\) 个祖先一定会导致 \(minlen(link(last))\) 减少至少 \(k-1\)，且加入完 \(n\) 个字符后显然 \(minlen(link(last))<n\)，故而这个操作的总时间复杂度是 \(O(n)\) 的。

---

数据范围 3 对应的解法

某个子串的出现次数显然为其 endpos 集合大小。

考虑在新加入某个字符时对 endpos 造成的影响，其对目前的后缀出现次数 +1 应该如何统计。由于所有的终止节点对应的子串对应了所有的后缀，也就是出现次数加一的所有子串，故而只需要在每次插入字符之后，将 \(cur\) 及其在 \(link\) 树上的祖先对应的出现次数加一即可。但是这样做复杂度无法保证。

考虑把整条链上出现次数加一的形式改为树上差分的形式，则每次只需要对 \(cur\) 的出现次数差分加上一，最后 dfs 或拓扑一遍后缀链接树即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2000010;
int p,q,i,l,r,ch,cl;
int lst=1,cur,tot=1;
int deg[maxn],que[maxn];
long long ans;
struct SamNode{
	int link,len,siz;
	int ver[26];
}N[maxn];
int main(){
	while(isalpha(ch=getchar())){
		ch-='a';cur=++tot;
		p=lst;N[cur].siz=1;
		N[cur].len=N[lst].len+1;
		while(p){
			if(q=N[p].ver[ch]) break;
			N[p].ver[ch]=cur;
			p=N[p].link;
		}
		if(!p) N[cur].link=1;
		else{
			if(N[q].len==N[p].len+1) N[cur].link=q;
			else{
				N[cl=++tot]=N[q];
				N[cl].siz=0;
				N[cl].len=N[p].len+1;
				N[q].link=N[cur].link=cl;
				while(N[p].ver[ch]==q){
					N[p].ver[ch]=cl;
					p=N[p].link;
				}
			}
		}
		lst=cur;
	}
	for(i=2;i<=tot;++i) ++deg[N[i].link];
	for(i=1;i<=tot;++i) if(!deg[i]) que[++r]=i;
	while(l!=r){
		i=que[++l]; N[N[i].link].siz+=N[i].siz;
		if(!(--deg[N[i].link])) que[++r]=N[i].link;
	}
	for(i=1;i<=tot;++i) if(N[i].siz>1) ans=max(1LL*N[i].siz*N[i].len,ans);
	printf("%lld",ans);
	return 0;
}

例题3 数据范围2：\(n\le 10^7\)。

对这个串建立 SAM。由于 SAM 上从起点出发的任意一条路径均对应了唯一的子串，所以每个点出发的路径条数就是有某个前缀的子串个数。在 SAM 的转移边组成的 DAG 上拓扑 dp 找到从每个点出发的路径条数。

考虑可重子串的计数。在求出每个节点对应的 endpos 之后，计算某个点开始的子串个数时，不能仅仅将这个点出发的路径条数相加。在 DAG 上从某个点向其前驱转移时，需要加上这个点的 endpos 大小（考虑这个前驱节点只加这一条转移边对应的字符的状态，此时需要取这个节点）。从根节点开始时不能减去对应大小（空串不计入排序）。

最后需要在 SAM 的 DAG 上 dfs 以按位确定答案的前缀。在 dfs 搜索到某个节点时，需要将 \(k\) 减去这个节点对应的 endpos（不可重计数则减 1），表示这个对应的前缀对答案造成的贡献，若此时 \(k\) 为负则已经求出答案。同时在节点上顺次访问转移边，将 \(k\) 减去目前扫描到的所有转移边对应的点的后缀数，直到 \(k\) 将在这一次操作时变为负，才不进行这次操作，而是确定答案当前位，并且访问这个子节点。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000010;
const int maxl=20000010;
char s[maxn];
int o,k,i,j,u,v,l=1,r,te;
int deg[maxl],que[maxl];
int h[maxl],nxt[maxn*3],ver[maxn*3];
int p,q,cl,ch;
int cur,lst=1,tot=1;
struct SamNode{
	int link,len,siz;
	int nxt[26];
	long long str,sum;
}N[maxl];
#define link(p) N[p].link
#define len(p) N[p].len
#define siz(p) N[p].siz
#define nxt(p) N[p].nxt
#define str(p) N[p].str
#define sum(p) N[p].sum
int main(){
	scanf("%s",s+1);
	N[1].str=1;
	for(i=1;s[i];++i){
		ch=s[i]-'a';
		cur=++tot;
		p=lst;
		siz(cur)=1;
		len(cur)=i;
		while(p){
			if(nxt(p)[ch]) break;
			nxt(p)[ch]=cur;
			p=link(p);
		}
		if(!p) link(cur)=1;
		else{
			q=nxt(p)[ch];
			if(len(q)==len(p)+1) link(cur)=q;
			else{
				N[cl=++tot]=N[q];
				len(cl)=len(p)+1;
				siz(cl)=0;
				link(q)=link(cur)=cl;
				while(p&&nxt(p)[ch]==q){
					nxt(p)[ch]=cl;
					p=link(p);
				}
			}
		}
		lst=cur;
	}
	scanf("%d%d",&o,&k);
	if(!o) for(i=1;i<=tot;++i) siz(i)=1;
	else{
		for(i=2;i<=tot;++i) ++deg[link(i)];
		for(i=2;i<=tot;++i) if(!deg[i]) que[++r]=i;
		while(l<=r){
			u=que[l++]; v=link(u);
			siz(v)+=siz(u);
			if(!(--deg[v])) que[++r]=v;
		}
	}
	for(i=1;i<=tot;++i) str(i)=siz(i);
	str(1)=siz(1)=r=0;l=1;
	for(i=1;i<=tot;++i){
		for(j=0;j<26;++j){
			if(nxt(i)[j]){
				++deg[i];
				ver[++te]=i;
				nxt[te]=h[nxt(i)[j]];
				h[nxt(i)[j]]=te;
			}
		}
	}
	for(i=1;i<=tot;++i) if(!deg[i]) que[++r]=i;
	while(l<=r){
		u=que[l++];
		for(i=h[u];i;i=nxt[i]){
			v=ver[i]; str(v)+=str(u);
			if(!(--deg[v])) que[++r]=v;
		}
	}
	if(k>str(1)){
		printf("-1");
		return 0;
	}
	u=1;
	for(;;){
		if(k<=siz(u)) return 0;
		k-=siz(u);
		for(i=0;i<26;++i){
			v=nxt(u)[i];
			if(!v) continue;
			if(str(v)<k) k-=str(v);
			else{
				putchar(i+'a');
				u=v; break;
			}
		}
	}
}

例题5

求多个串 \(S_1,S_2,\cdots,S_n\) 的本质不同子串个数。

数据范围1：\(\sum|S_i|\le 10^6\)。

可以把这些串用特殊的连接字符连接起来，然后求出其 height 数组，得出答案。方法可以参考例题3 数据范围1 的解法。

数据范围2：\(\sum|S_i|\le 10^7\)。

考虑线性时间复杂度的 SAM。我们需要对 SAM 的内容进行一些拓展以解决多个字符串的问题。

---

广义后缀自动机

定义

考虑“大部分可以用后缀自动机处理的字符串问题均可以拓展到 Trie 上”，可以先对于多个串建立 Trie 树，然后通过 Trie 树建立 SAM，以对多个字符串的信息进行整合。这种 SAM 又称广义 SAM。

有两种所谓伪广义 SAM：将所有模式串之间插入特殊连接字符的串的 SAM 和插完一个模式串后将 last 设为根节点的 SAM。通常伪广义后缀自动机的平均复杂度等同于广义后缀自动机的最差复杂度，面对大量的字符串时，伪广义后缀自动机的效率远不如标准的广义后缀自动机。

构造

注意广义 SAM 有在线和离线两种方法进行构造。

具体来讲，离线算法在建出的 Trie 树上 dfs/bfs，将 Trie 树上的节点插入到 SAM，此时以这个节点的父节点作为 last。因为在广义 SAM 中，某个字符串 \(s\) 的 endpos 的定义为 Trie 上的所有模式串中 \(s\) 的 endpos 的并集（每一个节点均可视为一个模式串）的集合。但是如果单纯说 Trie 上的 endpos 恐怕很难有人听得懂 广义 SAM 仍然满足普通 SAM 的大多数性质。不过由于 dfs 的时间复杂度为 \(O(\sum_{i\in Trie}dep_i)\)，在只给出 Trie 的情况下会被卡成 \(O(|Trie|^2)\)，某种极端情况如下（摘自 https://www.luogu.com.cn/paste/3oq8xx3b）：

假设某个 Trie 形如：（其中最长串 \(aa\cdots ab\) 的长度为 \(n\)）

则通过 dfs 构造这个 Trie 的广义 SAM 的过程如下：

而 bfs 的时间复杂度最坏就是 \(O(\sum |S_i|)\)，这也是伪广义 SAM 的平均时间复杂度。故而伪广义 SAM 的效率远不如广义 SAM。

在线做法：待补。（安利 这篇文章）

时间复杂度证明

待补。

---

由于广义 SAM 满足普通 SAM 的性质，故所有串的本质不同的子串数量即为 \(\sum len(i)-len(link(i))\)。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=10000010;
int n,i,j,t=1,l,r,u,v,p,q,c;
int trie[maxn][26],que[maxn];
char s[maxn]; 
long long ans;
struct SAM_Node{
	int link,len;
	int nxt[26];
}N[maxn<<1];
#define len(p) N[p].len
#define nxt(p) N[p].nxt
#define link(p) N[p].link
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%s",s+1);
		u=1;
		for(j=1;s[j];++j){
			v=trie[u][s[j]-'a'];
			if(!v) trie[u][s[j]-'a']=v=++t;
			len(v)=j;u=v;
		}
	}
	que[0]=1;
	while(l<=r){
		u=que[l++];
		for(i=0;i<26;++i){
			v=trie[u][i];
			if(!v) continue; p=u;
			while(p&&(!nxt(p)[i])){
				nxt(p)[i]=v;
				p=link(p);
			}
			if(!p) link(v)=1;
			else{
				q=nxt(p)[i];
				if(len(q)==len(p)+1) link(v)=q;
				else{
					N[++t]=N[q];
					len(t)=len(p)+1;
					link(v)=link(q)=t;
					while(p&&nxt(p)[i]==q){
						nxt(p)[i]=t;
						p=link(p);
					}
				}
			}
			que[++r]=v;
		}
	}
	for(i=1;i<=t;++i) ans+=len(i)-len(link(i));
	printf("%lld",ans);
	return 0;
}

---

后缀树（Suffix Tree）

定义

后缀树同样是可用于字符串匹配的结构。在匹配字符串时，同 KMP 等算法对模式串的处理不同，后缀树可以直接处理文本串。

考虑在文本串后面加上一个特殊字符，以独立后缀与其他子串；然后将这些后缀插入 Trie 树上。由于每个后缀的每个前缀刚好对应了字符串的所有子串，故而 Trie 上可以查询文本串的所有子串。但是构建 Trie 的时间复杂度可达到 \(O(n^2)\)（其中 \(n\) 为串长，下同）

后缀树可看成这个 Trie 上的特殊字符的转移边连向的所有节点组成的 虚树。

例如：\(iakioi\%\) （其中 \(\%\) 为处理时加入的特殊字符）的原后缀 Trie 和后缀树分别为：

构造

若 \(u\) 的父节点为 \(fa_u\)，连向的转移边上的字符串为 \(S\)，则令 \(u\) 节点对应的最长子串 \(longest(u)\) 为 \(longest(fa_u)+S\)，其对应的所有子串 \(f(u)\) 为 \(\{longest(fa_u)+(S_1\sim S_1),longest(fa_u)+(S_1\sim S_2),\cdots,longest(fa_u)+S\}\)。

可以发现 \(f\) 的所有子串的出现 头位置相同。可以发现在后缀树上满足 endpos 在 SAM 上的几乎所有性质，例如令 \(u\) 节点对应的子串的出现头位置为 \(headpos(u)\)，则显然 \(headpos(u)\subsetneq headpos(fa_u)\)。由于子串出现的头位置相同，就是它们的反串在原串的反串上的 endpos 相同。

故而可以构造原串反串的 SAM，SAM 的 link 树即为原串的后缀树。

应用

由于后缀树本质是所有后缀组成的 Trie 的虚树，故两个后缀的 LCP 就是它们在后缀树上的 LCA 对应的最长子串。同时 dfs 一遍后缀树即可得后缀数组。

---

引入

求串 \(s\) 中的回文子串数量。\(|s|\le 10^7\)。

做法

定义一个长为 \(2k-1(k\in N)\) 的回文串 \(s\) 的回文中心为 \(s_k\)。则子串 \(s_2\sim s_{2k-2}\)，\(s_3\sim s_{2k-3}\)，一直到 \(s_k\) 均为回文串，回文中心也均是 \(s_k\)。对于任意一个字符 \(s_b\)，若 \(s_{b-c}\sim s_{b+c}\) 非回文串，则 \(\forall p\ge c\)，\(s_{b-p}\sim s_{b+p}\) 也不会是回文串。故我们对于串的任意一个字符 \(s_p\)，求 \(\max_{k=0} (1+k\prod_{i=0}^k[s_{p+i}=s_{p-i}])\)（也就是以 \(s_p\) 为回文中心的最长回文串的长度的一半），即为 \(d_p\)，则所有奇回文串的长度/数量之和即为 \(\sum d_p\)。

对于偶回文串，直接在原串中每两个相邻的字符之间加上间隔符，以间隔符为回文中心的长度大于一的奇回文串就对应了原串中的偶回文串。注意这样后原串中的每个回文串均被计算了两遍，需要将 \(\sum d\) 除以 \(2\)。

不使用下述算法的情况下，一种简单的方法是 hash + 二分，单次处理一个 \(d\) 值的时间复杂度为 \(O(\log |s|)\)。

Manacher 算法

原理

为了方便，我们按照上述方式处理原串，在原串中每两个相邻的字符之间加上间隔符，这样就只用考虑奇回文串。令处理后的串长为 \(n\)。

考虑某个性质：在一个回文串中，若某个子串是回文串，则对称位置长度相同的子串也是回文串。由此可得：若某个回文串为 \(s_l\sim s_r\)，回文中心为 \(s_p\)，且 \(s_{p-i-d_{p-i}+1}\sim s_{p-i+d_{p-i}-1}\) 被完全包含在 \(s_{l+1}\sim s_{r-1}\) 内，记 \(rev(s)\) 为 \(s\) 的反串，则

\[\begin{aligned}&{\color{white}=\ }s_{p-i-d_{p-i}+1}\sim s_{p-i+d_{p-i}-1}\\&=rev(s_{p-i-d_{p-i}+1}\sim s_{p-i+d_{p-i}-1})\\&=rev(rev(s_{p+i-d_{p-i}+1}\sim s_{p+i-d_{p-i}-1}))\\&=s_{p+i-d_{p-i}+1}\sim s_{p+i-d_{p-i}-1}\end{aligned} \]

且由于 \(s_{p-i-d_{p-i}}\ne s_{p-i+d_{p-i}}\) 有 \(s_{p+i+d_{p-i}}\ne s_{p+i-d_{p-i}}\)，故 \(d_{p+i}=d_{p-i}\)。

故我们可以维护目前由 \(d_1\sim d_{i-1}\) 得出的右端最靠右的回文子串 \(s_l\sim s_r\)，以此从 \(d_1\sim d_{i-1}\) 推出 \(d_i\)。记 \(r(i)=l+r-i\)，分类讨论一下各种情况：

• \(i>r\)。此时显然只能暴力处理。
• \(s_{r(i)-d_{r(i)}+1}>l\)。由于 \(\frac{l+r}2<i\)，此时显然有 \(s_{r(i)-d_{r(i)}+1}<r\)。按上述的方式处理。
• \(s_{r(i)-d_{r(i)}+1}\le l\)。此时不能直接得出 \(d_i\)，但是由于 \(s_{r(i)-d_{r(i)}+1}\sim s_{r(i)+d_{r(i)}-1}\) 的子串 \(s_l\sim s_{2r(i)-l}\) 是回文串，我们可以得出 \(d_i\) 的下界为 \(r(i)-l+1\)。在这个下界的基础上，继续暴力处理即可。

综上，我们就得到了 Manacher 算法的全流程。同时由于第一种和第三种情况的暴力处理 \(x\) 位，新的 \(r\) 就会增加 \(x\)，且处理到最后一位时的 \(r\) 显然是 \(n\)，故整个算法的时间复杂度是 \(O(n)\) 的。同时这种方法较其他方法常数小得多，理解和操作也很简单。

代码实现中，\(d_p\) 为 \(\max_{k=0} k\prod_{i=0}^k[s_{p+i}=s_{p-i}]\)，但原理与上述相同。

模板代码

#include <bits/stdc++.h>
using namespace std;
char ch,p[22000030];
int d[22000030],i,l,r=-1,k,mx,siz=1;
bool o;
int main(){
	p[1]='T';
	for(;;){
		ch=getchar();
		if(ch<'a'||ch>'z') break;
		p[++siz]=ch;
		p[++siz]='M';
	}
	p[siz]='D';
	for(i=1;i<=siz;++i){
		if(i>r) k=1;
		else k=min(d[l+r-i],r-i+1);
		while(i-k>=0&&i+k<siz&&p[i-k]==p[i+k]) ++k;
		d[i]=k--;if(i+k>r){l=i-k;r=i+k;}
	}
	for(i=1;i<=siz;++i){
		o=!((i==d[i]+1)||(i+d[i]==siz));
		if(mx<d[i]-o) mx=d[i]-o;
	}
	printf("%d\n",mx);
	return 0;
}

---

引入

给定一个空串 \(s\)，每次在 \(s\) 的末尾加入一个字符，询问末尾为 \(s\) 末尾的回文子串个数。强制在线。保证最后 \(s\) 的总长度不超过 \(5\times 10^5\)。

回文树/回文自动机（PAM，Palindromic Tree/Palindromic AutoMaton）

特点

同 Manacher 对字符串处理，只考虑奇回文串不同，回文树同时处理长度为奇数和偶数的回文串，分别用两棵树维护。由于从根节点出发可以遍历到原串所有的本质不同的回文子串，故回文树又称回文自动机。

构造

同 SAM 一样，构造 PAM 时我们仍然可以采用增量法，依次插入原串的每一个字符。然而 PAM 本质上是两棵树，每个节点均只代表一个回文子串。

下面令 \(len(p)\) 表示 \(p\) 节点对应的回文子串长度，\(fail(p)\) 表示 \(p\) 节点对应的回文子串最长回文后缀对应的节点编号，\(son(p,c)\) 表示在 \(p\) 节点对应的回文子串 两边 加上字符 \(c\) 形成的回文子串对应的编号。

引理：

​ 每次在当前字符串后添加一个字符，若新增了回文串，则新增的本质不同的回文串最多只有只有一个；若有，就是添加字符后的字符串的最长回文后缀。

​ 证明：这个最长回文后缀的任意回文后缀一定会与其某个回文前缀对称，而这个回文前缀一定是原串的回文子串，在 PAM 内出现过。

同时这证明了 PAM 的点数为 \(O(n)\) 级别的。这也证明了一个字符串的所有回文子串的数量为 \(O(n)\) 的。由于 PAM 为两棵树的形态，故边数也是 \(O(n)\) 的。

具体地，最开始时没有插入字符，只有两个根节点（令奇回文串的根节点为 \(t_1\)，偶回文串的根节点为 \(t_0\)）。由于保证插入字符合法，故 \(len(t_1)=-1\)，\(len(t_0)=0\)。为何方便后面的操作，我们令 \(fail(t_1)=t_0\)，\(fail(t_0)=t_1\)。

令 \(last\) 为插入上一个字符之后，最长回文后缀的编号，\(last\) 开始时可以为 \(t_0\) 或 \(t_1\)。注意回文串两边删除一个字符后仍然是回文串（或是空串）。设当前插入的是字符串 \(s\) 的第 \(k\) 个字符 \(c\)，则我们需要从 \(last\) 开始不断跳 fail 直到找到第一个 \(p\) 满足 \(s_{k-len(p)-1}=c\)。

若 \(son(p,c)\) 存在，则这个最长后缀已经出现在之前的部分中。否则首先需要新建节点 \(q\) 代表这个新的最长回文后缀，然后将 \(son(p,c)\) 赋为 \(q\)，最后从 \(p\) 开始不断跳 \(fail\) 直到跳到第一个节点 \(p'\) 满足 \(s_{k-len_{p'}-1}=c\)（注意条件不是存在 \(son(p',c)\)，可能这个回文串在其他位置出现时两边有 \(c\)，如字符串 \(ccbbc\)），然后将 \(fail(q)\) 设为 \(son(p',c)\)。若直到跳到 \(t_0\) 再跳到 \(t_1\) 都没有找到 \(p'\)，则将 \(fail(q)\) 设为空串对应的节点 \(t_0\)。

此时将 \(fail(t_1)\) 设为 \(t_0\)，将 \(fail(t_0)\) 设为 \(t_1\) 的用途就体现出来了：若插入字符 \(c\) 之前的串形如为 \(c+A+c+B\)（其中 \(B\) 即为 \(p\) 代表的偶回文串，且不包含字符 \(c\)），则最后 \(fail(q)\) 应该为 \(son(t_1,c)\)，而 \(p\) 原本以 \(t_0\) 为根节点，若无 \(fail(t_0)=t_1\) 就难以实现较为简单的判别。而若原串为 \(A+c\) 的形式（其中 \(A\) 未出现过 \(c\)，\(A+c\) 为奇回文串），则最后我们需要将 \(son(t_0,c)\) 赋为 \(q\)，最后一步需要从 \(t_1\) 跳到 \(t_0\)。像这样的特例还有许多，这样做明显更简洁地处理了这些特例。

时间复杂度

考虑 \(len(fail(last))\) 的变化。可以发现每一次跳 fail 指针均会使当前的节点的 \(len\) 减少，而最后 \(len(fail(last))\) 一定小于 \(n\)，故时间复杂度均摊下来是 \(O(n)\) 的。和 SAM 的时间复杂度证明很像。

（辟谣：CF 上的 一篇博客 说时间复杂度为 \(O(n\log\Sigma)\)，其中 \(\Sigma\) 是字符集大小，因为用到了主席树维护转移边）

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=500010;
int ch,p,q,len,cur,lst,tot,ans; 
char s[maxn];
struct PAM_Node{
	int fail,len,dep;
	int nxt[26];
}N[maxn];
#define len(p) N[p].len
#define dep(p) N[p].dep
#define nxt(p) N[p].nxt
#define fail(p) N[p].fail
int main(){
	N[0].fail=tot=1;
	N[0].len=-1;
	for(;;){
		ch=getchar();
		if(ch<'a') return 0;
		ch=(ch-97+ans)%26;
		s[++len]=ch+97;
		p=lst;
		while(s[len-len(p)-1]!=ch+'a') p=fail(p);
		if(nxt(p)[ch]) lst=nxt(p)[ch];
		else{
			cur=++tot; len(cur)=len(p)+2;
			lst=p;p=fail(p);q=0;
			while((q!=1)&&(s[len-len(p)-1]!=ch+'a')){
				q=p;
				p=fail(p);
			}
			if(!nxt(p)[ch]) fail(cur)=1;
			else fail(cur)=nxt(p)[ch];
			dep(cur)=dep(fail(cur))+1;
			nxt(lst)[ch]=cur; lst=cur;
		}
		ans=dep(lst);
		printf("%d ",ans);
	}
	return 0; 
}

例题

初始有一个空串，利用下面的操作构造给定串 \(S\)。

1. 串开头或末尾加一个字符
2. 串开头或末尾加一个该串的逆串

求最小化操作数，\(|S|\le 10^5\)，字符集为 \(\{A,T,C,G\}\)。

解法（暂缺）

代码（暂缺）

---

引入：字符串匹配

给定字符串 \(S\) 和 \(T\)，查询 \(T\) 在 \(S\) 中所有出现的位置。（其中 \(S\) 称为文本串，\(T\) 称为模式串）显然暴力匹配的最坏时间复杂度是 \(O(|S||T|)\) 的。然而在题目中我们需要一种最坏情况 \(O(|S|+|T|)\) 左右的算法。

KMP 模式匹配（Knuth-Morris-Pratt）

字符串相关的某个思路即是某个字符串不可行时考虑其某个后缀是否可以。

考虑 \(S_1\sim S_i\) 与 \(T\) 最多匹配到了 \(P_i\) 位，也就是 \(P_i=\max\limits_{d=1}^i [S_{i-d+1}\sim S_i=T_1\sim T_d]\,d\)。显然在考虑 \(S_1\sim S_{i+1}\) 与 \(T\) 匹配时，有 \(P_{i+1}\le P_i+1\)。而若 \(S_{i+1}\ne T_{P_i+1}\) 时，考虑有哪些长度 \(l\) 满足 \(S_{i-l+1}\sim S_i=T_1\sim T_l\) 且 \(T_{l+1}=S_{i+1}\)，此时最大的 \(l\) 即为所求的 \(P_{i+1}-1\)。也就是说我们需要找到所有的满足 \(T_1\sim T_l=S_{i-l+1}\sim S_i=T_{P_i-l+1}\sim T_{P_i}\) 的 \(l\)，也就是满足 \(T_1\sim T_{P_i}\) 的长为 \(l\) 的 真前缀（非 \(T\) 本身 的前缀）就是长为 \(l\) 的 真后缀（非 \(T\) 本身 的后缀）的 \(l\)（其中每个 \(i\) 对应的最长的 \(l\) 组成的数组称为 \(T\) 的 前缀函数，此处用 \(nxt\) 表示。特别地，\(nxt_0=nxt_1=0\)）。根据定义，最大的 \(l\) 是 \(nxt_{P_i}\)，考虑之后的 \(l\) 应该如何选择。

引理：仅次于 \(nxt_{P_i}\) 的 \(l\) 一定是 \(nxt_{nxt_{P_i}}\) 而不会是 \((nxt_{nxt_{P_i}},nxt_{P_i})\) 之间的任意一个值。

证明：若 \(\exists\,l\in(nxt_{nxt_{P_i}},nxt_{P_i})\)，则 \(T_1\sim T_l=T_{P_i-l+1}\sim T_{P_i}=T_{nxt_{P_i}-l+1}\sim T_{nxt_{P_i}}\)，而 \(nxt_{nxt_{P_i}}=\max\limits_{d=1}^{nxt_{P_i}}[T_{nxt_{P_i}-d+1}\sim T_{nxt_{P_i}}=T_1\sim T_d]\,d\)，此时 \(l\) 大于 \(nxt_{nxt_{P_i}}\) 且满足 \(nxt_{nxt_{P_i}}\) 满足的条件，与 \(nxt\) 的定义矛盾。故而仅次于 \(nxt_{P_i}\) 的 \(l\) 一定是 \(nxt_{nxt_{P_i}}\)。

此时可以令 \(p=P_i\)，若 \(S_{i+1}\ne T_{p+1}\)，则 \(p\leftarrow nxt_p\)，不断进行此操作直到 \(p=0\) 或 \(S_{i+1}=T_{p+1}\)。若 \(p=0\) 时仍然 \(S_{i+1}\ne T_{p+1}\)，则 \(P_{i+1}\) 为 \(0\)，否则 \(P_{i+1}\) 为 \(p+1\)。由于 \(\forall i,0\le nxt_i<i\) 且 \(P_{i+1}\le P_i+1\)，故最后计算 \(P\) 的时间复杂度为 \(O(|S|)\) 的。

考虑 \(nxt\) 的求法。我们发现 \(nxt\) 就是 \(T\) 和自己进行上述过程（此时 \(P\) 数组即为 \(nxt\) 数组），但是强制从第 \(2\) 位进行匹配。同样进行上述操作即可。故而总的时间复杂度是 \(O(|S|+|T|)\) 的。

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
char s1[maxn],s2[maxn];
int i,j,nxt[maxn];
int main(){
	scanf("%s%s",s1+1,s2+1);
	const int siz1=strlen(s1+1);
	const int siz2=strlen(s2+1);
	for(i=2;i<=siz2;++i){
		while(j&&s2[i]!=s2[j+1]) j=nxt[j];
		if(s2[i]==s2[j+1]) ++j;nxt[i]=j;
	}
	j=0;
	for(i=1;i<=siz1;++i){
		while(j&&(s1[i]!=s2[j+1]||j==siz2)) j=nxt[j];
		if(s1[i]==s2[j+1]) ++j;
		if(j==siz2){printf("%d\n",i-siz2+1);j=nxt[j];}
	}
	for(i=1;i<=siz2;++i) printf("%d ",nxt[i]);
	return 0;
}

循环字符串

相关定理1

对长为 \(n\) 的字符串 \(s\) 跑一遍 KMP 之后，若 \(n\bmod (n-nxt_n)=0\)，则 \(s\) 的最小循环节长度为 \(n-nxt_n\)。

证明1

若 \(s\) 的最小循环节长度为 \(a\)，则必有其长度为 \(n-a\) 的前缀和后缀完全相同，也就是 \(nxt_n\) 至少为 \(a\)。

如果此时 \(nxt_n\) 小于 \(a\)，（令 \(b=n-nxt_n\)）令 \(t\) 为 \(s\) 的长为 \(a\) 的前缀（只有此处下标从 \(0\) 开始），有 \(t_bt_{b+1}\cdots t_{a-1}t_0t_1\cdots t_{b-1}=t_0t_1\cdots t_{a-1}\)，也就是 \(\forall i\in[0,a-1],t_i=t_{(i+b)\bmod a}\)；由裴蜀定理可得 \(\exists p>0\) 对 \(\forall i\in[1,n]\)，都有 \(t_i=t_{(i+pb)\bmod a}=t_{(i+\gcd(a,b))\bmod a}\)；故 \(t\) 和 \(s\) 的最小循环节长度均为 \(\gcd(a,b)\)，与之前矛盾。

证毕。

相关定理2

长为 \(n\) 的任意字符串 \(s\) 的所有循环节长度一定都是最小循环节长度的整数倍。

证明2

思路与 证明 1 相似。

令 \(s\) 的最小循环节长度为 \(a\)；若 \(s\) 存在长度为 \(b\) 的循环节，且 \(b\bmod a\ne 0\)，则 \(n\ge \rm{lcm}(a,b)\)；由裴蜀定理得 \(\exists j\ge 0,\forall i\in[0,a-1],s_i=s_{i+aj}=s_{(i+aj)\bmod b}=s_{i+\gcd(a,b)}\)，且 \(j<\frac{\rm{lcm}(a,b)}a\)。所以 \(s\) 由长度为 \(\gcd(a,b)\) 的循环节，而 \(\gcd(a,b)<a\)；与之前矛盾。

证毕。

AC 自动机（Alfred-Corasick Automaton）

原理

AC 自动机结合了 Trie 树能整理多个字符串的特性和 KMP 算法中的前缀函数的性质，常用于对多个字符串的信息的整合（例如多模式串匹配）。

构造和理解

AC 自动机上除了需要对于多个串建出普通的 Trie 之外，每个节点还需要一个 nxt 指针，表示这个节点对应的字符串在 Trie 存在的最长后缀的对应节点。

nxt 指针的求法、原理和原理证明与 KMP 算法中的 nxt 相似。在计算某个节点 \(u\) 的 nxt 时，令其父节点为 \(p\)，父节点连向这个点的转移边为字符 \(c\)（令 \(trie_{p,c}=u\)），若 \(trie_{nxt_p,c}\) 存在，则令 \(nxt_u\leftarrow trie_{nxt_p,c}\)；否则 \(p\leftarrow nxt_p\)，再看 \(trie_{nxt_p,c}\) 是否存在；直到 \(p\) 为根节点且 \(trie_{p,c}\) 不存在，再将 \(nxt_u\) 赋值为根节点。

显然 \(\forall i\)，\(nxt_i\) 对应的字符串长度小于 \(i\)，故而可以在 Trie 树上 BFS，可以保证在求每个点的 nxt 时其父节点的 nxt、这个 nxt 对应的 nxt …… 这样即可顺利求这个点的 nxt。不难发现 nxt 组成了一棵内向树。（p.s. 这种树被称为 失配树。）

考虑另外一种情况：在模式串为 she、he、her，对文本串 sher 进行匹配。在匹配完 she 之后需要标记 she、he（某个模式串得以完整匹配时，其所有后缀也能完整匹配），同时需要从 Trie 树上的 she 串的节点和其 nxt 上同时走，才能匹配出模式串 her。如果真的在目前经过的节点的所有 nxt 一起根据字符跳转的话，这样会是很低效的。

如果需要更方便地进行跳转，Trie 树边是不够的，我们需要在求出的 nxt 的基础上多连一些转移边。此时需要的就是 \(\forall u,c\)，若不存在 \(trie_{u,c}\)，则增加从 \(u\) 到 \(trie_{nxt_u,c}\) 的 \(c\) 转移边。这样等效于在从 \(u\) 走到 \(trie_{u,c}\) 时，若这条转移边非树边，则相当于同时在 \(nxt_u\)、\(nxt_{nxt_u}\)（因为 \(nxt_u\) 也进行了这样的过程）等节点均进行了转移，在后面补上 \(c\)。

最后进行多模式匹配的过程就是将文本串在 AC 自动机上匹配的过程。在文本串进行匹配时，标记每个点被经过的次数。理论上某个点被经过时我们需要标记其 nxt 树上的所有祖先（但是这样会使得时间复杂度升为 \(O(n^2)\)，考虑模式串刚好为 \(aa\cdots aa\) 的情况），但是可以在跑完文本串后再进行标记。时间复杂度显然为 \(O(n|\Sigma|)\) 的，其中 \(|\Sigma|\) 为字符集大小。

AC 自动机模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=2000010;
const int maxl=2000010;
int i,j,n,k,t,*p,hd,tl,siz,tot,ans,all;
int trie[maxn][26],q[maxn],ed[maxn],nxt[maxn];
int To[maxn],In[maxn],cnt[maxn];
char s[maxn],d[maxl];
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%s",s+1);
		siz=strlen(s+1);
		p=&k;
		for(j=1;j<=siz;++j){
			p=&trie[*p][s[j]-'a'];
			if(!(*p)) *p=++tot;
		}
		To[i]=*p;
	}
	for(i=0;i<26;++i) if(trie[0][i]) q[++tl]=trie[0][i];
	while(hd!=tl){
		i=q[++hd];
		for(j=0;j<26;++j){
			p=&trie[i][j];
			if(!(*p)) *p=trie[nxt[i]][j];
			else{nxt[*p]=trie[nxt[i]][j];q[++tl]=*p;}
		}
	}
	hd=tl=j=0;
	for(i=1;i<=tot;++i) ++In[nxt[i]];
	for(i=1;i<=tot;++i) if(!In[i]) q[++tl]=i;
	scanf("%s",d+1);
	siz=strlen(d+1);
	for(i=1;i<=siz;++i){
		j=trie[j][d[i]-'a'];
		++cnt[j];
	}
	while(hd!=tl){
		i=q[++hd];j=nxt[i];
		cnt[j]+=cnt[i];
		if(!(--In[j])) q[++tl]=j;
	}
	for(i=1;i<=n;++i) printf("%d\n",cnt[To[i]]);
	return 0;
}

---

引入

给定一个长度为 \(n\) 的正整数序列 \(a\) ，有 \(q\) 次询问，第 \(i\) 次询问给定一个长度为 \(L_i\) 的序列 \(b_i\)，请你判断 \(b_i\) 是不是 \(a\) 的子序列。序列 \(a\) 和所有 \(b_i\) 中的元素都不大于一个给定的正整数 \(m\)。

\(1 \leq n, m, q \leq 10^5\)，\(1 \leq a_i, b_{i, j} \leq m\)，\(1 \leq l_i \leq 10^6\)，\(\sum_{i = 1}^{q} l_i \leq 10^6\)。

做法

考虑维护一个能够维护某个串的所有本质不同的子序列的自动机。

---

序列自动机

可能是最简单构造/理解的，附加内容最少的自动机。

构造

考虑贪心。对于一个串 \(s\)，从某个位置开始维护子序列时，显然让每个字符均在 \(s\) 尽可能靠前的位置出现时，后面能够接的子序列数会尽量多。这样不会减少能够构造的数量的子序列数量。

设 \(son(i,c)\) 表示 \(s_i\) 之后第一个字符 \(c\) 出现的位置。将 \(son(i,c)\) 抽象成转移边，则所有的 \(son\) 转移边构成了自动机。而 \(son\) 的求法也很简单，逆推即可：

\[son(i,c)=\begin{cases}son(i+1,c)&s_{i+1}\ne c\\i+1&s_{i+1}=c\end{cases} \]

字符集较大时，可以用主席树维护转移边。

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxl=18;
const int maxn=1000010;
int n,m,q,i,lt,rt,mt,pt,qt,tot;
int a[maxn];
struct node{
	int ls,rs,val;
}tr[maxn*maxl];
#define ls(p) tr[p].ls
#define rs(p) tr[p].rs
#define val(p) tr[p].val
int root[maxn];
int main(){
	scanf("%d",&n);
	scanf("%d%d%d",&n,&q,&m);
	for(i=1;i<=n;++i) scanf("%d",a+i);
	root[n]=tot=1;
	for(i=n;i;--i){
		pt=root[i-1]=++tot;
		lt=1;rt=m;qt=root[i];
		while(lt<rt){
			tr[pt]=tr[qt];
			mt=(lt+rt)>>1;
			if(a[i]<=mt){
				ls(pt)=++tot;
				rt=mt;qt=ls(qt);
			} 
			else{
				rs(pt)=++tot;
				lt=mt+1;qt=rs(qt);
			}
			pt=tot;
		}
		val(pt)=i;
	}
	while(q--){
		scanf("%d",&n);
		for(i=1;i<=n;++i) scanf("%d",a+i);
		pt=root[0];
		for(i=1;i<=n;++i){
			lt=1;rt=m;
			while(lt<rt){
				mt=(lt+rt)>>1;
				if(a[i]<=mt){
					pt=ls(pt);
					rt=mt;
				}
				else{
					pt=rs(pt);
					lt=mt+1;
				}
			}
			pt=val(pt);
			if(!pt){
				printf("No\n");
				break;
			}
			else pt=root[pt];
		}
		if(pt) printf("Yes\n");
	} 
	return 0;
}

例题：

给出字符串 \(S\)，计算其本质不同的子序列数，答案取模。\(|S|\le 3\times 10^5\)。

附加内容1：无。

直接求自动机上不同路径数即可。

附加内容2：求其 \(k\) 小子序列。\(k\le 10^{18}\)。

附加内容2.5：\(k\le 10^9,|S|\le 10^6\)。

在子序列自动机的 DAG 上找出从某个点出发的路径条数（根节点之外的点的路径条数要加一），大于 \(k\) 的直接赋为 \(\inf\)（打 \(\inf\) 标记），然后模拟 dfs 过程，按位填字符即可，方法可以参照 弦论 的做法。注意原题空间只有 128MB，故在 DAG 上 dp 找路径条数时，不应该建反图然后拓扑 dp，而是 dfs 以递归查找。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1000010;
const int maxx=1000000000;
const int Inf=1000000001;
int n,k,i,j,l,r,u,v,tot;
int num[maxn],nxt[maxn][26];
char s[maxn];
bool vis[maxn];
void dfs(int p){
	if(vis[p]) return;
	vis[p]=1;
	int lp,to;
	for(lp=0;lp<26;++lp){
		to=nxt[p][lp];
		if(!to) continue;
		dfs(to);
		num[p]+=num[to];
		if(num[p]>maxx){
			num[p]=Inf;
			return;
		} 
	}
}
int main(){
	scanf("%d%d%s",&n,&k,s+1);
	for(i=n;i;--i){
		num[i]=1;
		for(j=25;j>=0;--j) nxt[i-1][j]=nxt[i][j];
		nxt[i-1][s[i]-'a']=i;
	}
	dfs(0);
	++k;
	for(;;){
		if(k==1) return 0;
		--k;
		for(j=0;j<26;++j){
			v=nxt[u][j];
			if(!v) continue;
			if(k<=num[v]){
				u=v;
				putchar(j+'a');
				break;
			}
			else k-=num[v];
		}
	}
	return 0;
}

附加内容3：\(q\) 组询问，每次询问第 \(k\) 小子序列的最后 \(r\) 个字符。\(k\le 10^{18},q\le 10^5,\sum r\le 10^6\)。

待补。

---

最小表示法

定义

求 \(\text{argmin}_{i=1}^n (S_i\sim S_n+S_1\sim S_{i-1})\)。通俗地说，不断将字符串末尾的字符移到开头，得到的 \(n\) 个字符串中的字典序最小者即为字符串的 最小表示。

暴力求法

在得知 \(i\in[1,k)\) 时使得 \(S_i\sim S_n+S_1\sim S_{i-1}\) 最小的 \(i\) 时，可以直接将其和 \(S_k\sim S_n+S_1\sim S_{k-1}\) 比较，得出 \(i\in[1,k]\) 时使得 \(S_i\sim S_n+S_1\sim S_{i-1}\) 最小的 \(i\)。虽然随机数据下表现良好，但是可以构造形如 \(aa\cdots ab\) 的数据将其卡成 \(O(n^2)\)。

后缀数组

求出 \(S_1\sim S_n+S_1\sim S_n\) 的后缀数组，然后 \(1\sim n\) 中 \(rk\) 最小者即为最小表示。证明显然。

\(O(n)\) 做法

原理

令 \(f(i)=S_i\sim S_n+S_1\sim S_{i-1}\)，若 \(f(i)>f(j)\) 且 \(f(i)_1\sim f(i)_k=f(j)_1\sim f(j)_k\)（令 \(g(i,j)=\max_{k=1}^n[f(i)_1\sim f(i)_k=f(j)_1\sim f(j)_k]\cdot k\)），则 \(\forall p\in[1,k],f(i+k)>f(j+k)\)。也就是 \(\forall p\in[i,i+k]\)，\(p\) 均不会成为最小表示。

做法

仍然是维护当前的最小表示 \(i\) 和对应的集合 \([1,j]\)。比较 \(f(i)\) 和 \(f(j+1)\)，如果 \(f(i)<f(j+1)\)，则将 \(j\) 赋为 \(j+g(i,j+1)+1\)，否则将 \(i\) 赋为 \(j+1\)，将 \(j\) 赋为 \(\max(j+1,i+g(i,j+1)+1)\)。

时间复杂度

模板代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=300010;
#define Md(p) ((p)>=n?(p)-n:(p))
int n,i,j,k,p;
int a[maxn]; 
int main(){
	scanf("%d",&n);
	for(i=0;i<n;++i) scanf("%d",a+i);
	i=0;
	for(j=1;j<n;++j){
		k=0;
		while(k<=n&&a[Md(i+k)]==a[Md(j+k)]) ++k;
		if(a[Md(i+k)]>a[Md(j+k)]){
			p=j;
			j=max(j,i+k);
			i=p;
		}
		else j=j+k;
	}
	for(j=0;j<n;++j) printf("%d ",a[Md(i+j)]);
	return 0;
}

---

标签：nxt,后缀,int,知识,整理,maxn,字符串,link,sim
From： https://www.cnblogs.com/FrancaisDrakeCwoi/p/16753594.html