字符串

之前就是史，重新来写，字符串还是有必要学的。

KMP

用于文本串匹配。其和暴力的区别在于失配后会从一个特定位置重新开始匹配而不是从头开始，从而节约时间。
这个失配数组也就是 \(nex_i\) 表示 \(S[\mathbf{1}\dots i]\) 的最长 \(\mathtt{border}\) 长度，建出来之后相当于一个自动机。
记住代码实现就行了，实际上大部分情况也可以二分哈希替代，但毕竟多个 \(\mathtt{log}\)。
模板题代码：

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=1145140,M=1919810,inf=2147483646;
ll n,m;
char s[N],t[N];
ll nex[N];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>(s+1)>>(t+1);
	n=strlen(s+1),m=strlen(t+1);
	ll p=0;
	for(int i=2;i<=m;++i){
		while(p&&t[i]!=t[p+1]) p=nex[p];
		if(t[i]==t[p+1]) ++p;
		nex[i]=p;
	}
	p=0;
	for(int i=1;i<=n;++i){
		while(p&&s[i]!=t[p+1]) p=nex[p];
		if(s[i]==t[p+1]) ++p;
		if(p==m){
			cout<<i-m+1<<'\n';
			p=nex[p];
		}
	}
	for(int i=1;i<=m;++i) cout<<nex[i]<<" ";
	return 0;
}

P3426

一个思维题，只需要KMP，不需要后缀数据结构也能做。
首先读完题可以发现，满足题意的子串一定是原串的 \(\mathtt{border}\)。暴力的想法就是去枚举所有 \(\mathtt{border}\) 然后用 KMP 判断匹配的位置之差是否大于串的长度。
考虑进行 dp（想到这一步有点跳跃），设 \(dp[i]\) 为前 \(i\) 个字符的最小答案。对于某个 \(nex_i=\mathbf{0}\)，也就是没有 \(\mathtt{boeder}\) 的情况时，就只能 \(dp_i=i\)，这是显然的。然后考虑答案转移，经过手玩可以发现，\(dp[i]=dp[nex[i]]\)，这是可以证明的，但我懒。
那么转移关系就是 \(dp[i]=i\) 或 \(dp[i]=dp[nex[i]]\)。当前面有一个点 \(j\) 可以被 \(dp[nex[i]]\) 覆盖到且能覆盖到当前要覆盖的后缀部分，那么 \(dp[i]\) 就可以从 \(dp[nex[i]]\) 转移过来，这样是一定不劣的。维护这个过程的话可以开一个桶来记录每种长度的 \(\mathtt{border}\) 最多能覆盖到哪里。

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=5*114514,M=1919810,inf=2147483646;
ll n;
char s[N];
ll nex[N],dp[N],bu[N]; //前i个字符的答案 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>(s+1); n=strlen(s+1);
	ll p=0;
	for(int i=2;i<=n;++i){
		while(p&&s[i]!=s[p+1]) p=nex[p];
		if(s[i]==s[p+1]) ++p;
		nex[i]=p;
	}
	dp[1]=bu[1]=1;
	for(int i=2;i<=n;++i){
		if(bu[dp[nex[i]]]+dp[nex[i]]>=i){
			dp[i]=dp[nex[i]];
			bu[dp[nex[i]]]=i;
		}
		else dp[i]=bu[i]=i;
	}
	cout<<dp[n];
	return 0;
}

后缀自动机（SAM）

定义不想多写了，感性理解，SAM 就是个可以 \(O(n)\) 构造并在上面可以 \(O(n)\) 完成操作的有向图，存了原串所有的后缀，有很多有用的性质，能拿来做很多题。

结束位置 \(\mathtt{endpos}\)

对于原串 \(s\) 的任意非空子串 \(t\)，其 \(\mathtt{endpos}(t)\) 为 \(t\) 在 \(s\) 中的所有结束位置。两个子串 \(t_{\mathtt{1}},t_{\mathtt{2}}\) 的 \(\mathtt{endpos}\) 集合可能相等，这样我们可以把所有字串根据 \(\mathtt{endpos}\) 集合划分为若干个等价类。
显然，SAM 中的每个状态对应一个或多个 \(\mathtt{endpos}\) 相同的子串。换句话说，SAM 中的状态数等于所有子串的等价类的个数，再加上初始状态。SAM 的状态个数等价于 \(\mathtt{endpos}\) 相同的一个或多个子串所组成的集合的个数 \(\mathtt{+1}\)。同时关于 \(\mathtt{endpos}\) 有一些性质，我就简略写了，一下都考虑 \(s\) 的两个子串 \(u,w\) 并假设 \(|u|\le|w|\)：

\(\mathbf{1}\).若 \(\mathtt{endpos}(u)\cap\mathtt{endpos}(w)=\oslash\)，则 \(u\) 不是 \(w\) 后缀，反之则是。

\(\mathbf{2}\).一个等价类中的所有串的长度的集合恰能覆盖一整段区间 \([x,y]\)。

后缀链接 \(\mathtt{link}\)

有点像 AC自动机的失配链接。

待补。