我想，字符串的艺术，是在走过的字符上留下路标，让每一次眺望，都成为对过往的回应。
——Zhl

Manacher

P3805 【模板】Manacher

首先暴力就是直接对于每一个点向外扩展。

然后需要优化，就是利用已知的更新未知的。

首先我们现在在节点 $i$ ，然后我们记录下了右节点最远的一个回文串， $l\to mid \to r$ 。

分类讨论：

$mid < i< r$ ，此时，我们可以用 $i$ 关于 $mid$ 对称的点来更新 $i$ ，然后超出原来的对称区间的直接暴力。
$r\le i$ 直接暴力扩展。

因为右边界扩展时 $O(n)$ 的，所以算法复杂度 $O(n)$ 。

然后一个经典的实现就是为了防止判断奇偶，直接在两两之间塞 #。

所以 Manacher 的核心思想在于前面的信息怎么对后面有用。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
char c[11000010],s[22000010];
int p[22000010],cnt=0;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>(c+1);
	n=strlen(c+1),s[++cnt]='#',s[++cnt]='#';
	for(int i=1;i<=n;i++)s[++cnt]=c[i],s[++cnt]='#';n=cnt;
	int mid=0,r=0;
	for(int i=1;i<=n;i++){
		if(i<=r)p[i]=min(p[mid*2-i],r-i+1);
		while(s[i-p[i]]==s[i+p[i]])p[i]++;
		if(p[i]+i-1>r)r=p[i]+i-1,mid=i;
		ans=max(ans,p[i]);
	}
	cout<<ans-1<<endl;
	return 0;
}

KMP

之前的讲解。

P3375 【模板】KMP

P3375 【模板】KMP。

KMP 的思想主要是有一个 kmp 数组，然后记录匹配失败后，需要移动到哪里。

每一个位置只需要进行一次比较。

然后代码比较直观。

代码

C++

#include<bits/stdc++.h>
#define int long long
using namespace std;
char s[1000010],t[1000010];
int kmp[1000010];


signed main(){
	cin>>(s+1)>>(t+1);
	int n=strlen(s+1),m=strlen(t+1);
	int j=0;
	for(int i=2;i<=m;i++){
		while(j&&t[j+1]!=t[i])j=kmp[j];
		if(t[i]==t[j+1])j++;
		kmp[i]=j;
	}
	j=0;
	for(int i=1;i<=n;i++){
		while(j&&s[i]!=t[j+1])j=kmp[j];
		if(t[j+1]==s[i])j++;
		if(j==m){
			cout<<i-m+1<<'\n';
			j=kmp[j];
		}
	}
	for(int i=1;i<=m;i++)cout<<kmp[i]<<' ';
	cout<<'\n';
	
	return 0;
}

P2375 [NOI2014] 动物园

P2375 [NOI2014] 动物园。

这道题我们需要在长度超限的情况下 $j=kmp_j$ 。

然后问的是数量，就直接在预处理的时候处理出来，表示子串中符合的个数（对长度没有限制）。

扩展 KMP

P5410 【模板】扩展 KMP / exKMP（Z 函数）。

这篇 TJ 讲的清楚，C 过来。

结论： 对于 $i>0$ ，对任意 $0\le l<i$ 都可以递推得：

$\forall 0\le x<\min(z(i-l),l+z(l)-i),s[(i)+(x)]=s[(0)+(x)]$

证明：

主要思想是将这个位置转换成前面的一个位置加上一个位移，然后这个位置的 $z$ 函数我们是知道的，只需要移动到 $0$ 就可以转换成下一个函数了。

\begin{aligned} &s[(i)+(x)]\\ =&s[(l)+(i+x-l)]\\ =&s[(0)+(i+x-l)]\color{red}{(x\le l+z(l)-i)}\\ =&s[(i-l)+(x)]\\ =&s[(0)+(x)]\color{red}{(x\le z(i-l))}\\ \end{aligned}

初始化 $z(i)=\min(z(i-l),l+z(l)-i)$ ，然后暴力判断字符相等增加 $z(i)$ 。

这里 $l$ 选满足 $j+z(j)(0\le j<i)$ 最大的 $j$ ，这样每个字符只会被暴力判断一次（如果最小值是 $z(i-l)$ 就会第一次就失配），所以时间复杂度可以做到 $\Theta(n)$ 。

对于题目中的问题其实把 $b$ 和 $a$ 接起来做个 $z$ 就可以了。

最小表示法

P13270 【模板】最小表示法。

先断环成链放两个。

先放 $i$ 和 $j$ ，表示最小的和当前的（下标小的设置为最小的）。

然后如果 $i$ 是最小的，然后现在有来了一个 $j$ ，先把能匹配的 $k$ 位匹配。

如果 $i$ 更小， $j$ 就变成 $j+k+1$ ，因为这中间的一定比 $i$ 到 $i+k+1$ 中间的某一个大（他们匹配了一些位置了）。

如果 $j$ 更小， $i$ 变成 $i+k+1$ 。

复杂度易证。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n;
char s[20000010];



signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	cin>>(s+1);
	for(int i=1;i<=n;i++){
		s[i+n]=s[i];
	}
	int i=1,j=2;
	for(;i<=n&&j<=n;){
		int k=0;
		while(k<=n&&s[i+k]==s[j+k])k++;
		if(s[i+k]>s[j+k]) i+=k+1;
		else j+=k+1;
		if(i==j)j++;//不要漏 
	}
	int ans=min(i,j);
	for(int i=ans;i<=ans+n-1;i++)cout<<s[i];
	cout<<endl;
	
	return 0;
}

AC 自动机

P5357 【模板】AC 自动机

P5357 【模板】AC 自动机。

AC 自动机是一个基于 Trie，结合 KMP 思想的算法。

首先，先对模式串建立一个 Trie。

fail 指针

然后我们需要定义一个失配指针 $fail$ ， $fali_u$ 指向 $v$ 表示 $v$ 是 $u$ 的最长在 Trie 树存在的后缀（从根节点开始的路径）。

与 KMP 不同，KNP 表示最长相同的前后缀。

所以有可能 $fail$ 的指针指向另一个模式串。

指针计算

类比一下 KMP。

我们发现这一类字符串的主要思想就是用已知更新未知。

首先，我们现在在 $u$ ，然后它的父节点是 $p$ ， $p$ 通过字符 $c$ 的边指向 $u$ ，即 $trie(p,c)=u$ 。分类讨论：

如果 $trie(fail_p,c)$ 存在，那么我们就可以在 $fail_p$ 和 $p$ 之后扩展一下，就可以让 $fail_u$ 指向 $trie(fail_p,c)$ 了。
否则，我们继续找到 $trie(fail_{fail_p},c)$ ，一直重复，直到匹配成功或者到达根节点。

然后我们就能写出预处理函数了，询问的话就用 KMP 类似思路就行了。

询问我们失配的时候就指向 $fail_u$ ，就是最大限度利用已经匹配的东西，找最大的后缀继续。

优化

我们发现这样暴力跳回超时，所以我们需要优化一下。

直接拓扑排序，也就是先遍历会对后面有贡献的。

P2444 [POI 2000] 病毒

P2444 [POI 2000] 病毒。

这道题中，只需要建完 AC 自动机的 Trie 后，判断是否又有不经过插入字符串的最后一个节点的环就行了。

然后有一个需要注意的地方就是需要 ed[v]|=ed[fail[v]]，因为如果如果一个节点的一个后缀是病毒，这个节点也是。

P3041 [USACO12JAN] Video Game G

P3041 [USACO12JAN] Video Game G。

AC 自动机 + DP。

$f_{i,j}$ ：长度为 $i$ ，在 AC 自动机节点 $j$ 的最大得分。

f_{i+1,v} = \max\{f_{i,j} + val_v\}

$val$ 就是走到 $v$ 能获得的权值。

P4052 [JSOI2007] 文本生成器

P4052 [JSOI2007] 文本生成器。

AC 自动机上 dp。

容斥一下， $f_{i,j}$ 表示长度为 $i$ ，在 $j$ 的时候的情况数。

f_{i+1,tr_{j,x}}\gets f_{i,j}

回文树

P5496 【模板】回文树 / 回文自动机（PAM）

P5496 【模板】回文树 / 回文自动机（PAM）。

基础形态

我们想知道一个字符串是不是回文串，可以根据它的字串来判断。

我们利用回文字符串这样性质把它们放到树上。

长度为奇数的回文子串有中心，而长度为偶数的回文子串没有，所以回文树有两个初始的状态， $0$ 和 $-1$ 分别表示奇根和偶根，与 AC 自动机的根作用差不多。

构建回文自动机的方法就是，根节点到这个节点表示这个回文串的一半。

线性状态数证明

我们需要证明树的大小是线性的。

~~直接扒 OI-WIKI 的~~。

我们需要先证明：对于一个字符串 $s$ ，它的本质不同回文子串个数最多只有 $|s|$ 。

当 $|s| >1$ 时，设 $t=s+c$ ，其中 $t$ 表示 $s$ 最后增加一个字符 $c$ 后形成的字符串。

假设结论对 $s$ 串成立．考虑以最后一个字符 $c$ 结尾的回文子串，假设它们的左端点由小到大排序为 $l_1,l_2,\dots,l_k$ 。

由于 $t[l_1..|t|]$ 是回文串，因此对于所有位置 $l_1 \le p \le |t|$ ，有 $t[p..|t|]=t[l_1..l_1+|t|-p]$ ．所以，对于 $1 < i \le k$ ， $t[l_i..|t|]$ 已经在 $t[1..|t|-1]$ 中出现过，因此，每次增加一个字符，本质不同的回文子串个数最多增加 $1$ 个。

构建方法

初始阶段，偶根的 $fail$ 指向奇根。

我们考虑一个一个插入，现在树里面已经有了 $s_1\to s_{i-1}$ ，然后我们现在要插入 $s_i$ 。

我们从以上一个字符结尾的最长回文子串对应的节点开始，不断沿着 fail 指针走，直到找到一个节点满足 $s_{p}=s_{p-len-1}$ ，即满足此节点所对应回文子串的上一个字符与待添加字符相同。

代码

C++

#include<bits/stdc++.h>
using namespace std;
int n;
char s[500010];
int len[500010],t[500010][26],tot=1,fail[500010],num[500010],now=0;
int getfail(int x,int i){
	while((i-len[x]-1<1)||s[i-len[x]-1]!=s[i])x=fail[x];
	return x;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>(s+1);
	n=strlen(s+1);
	fail[0]=1;
	len[1]=-1;
	int lastans=0;
	for(int i=1;i<=n;i++){
		//if(i>=2)s[i]=(char)(s[i]+lastans-97)%26+97;
		if(i>=2)s[i]=(char)((s[i]+lastans-97)%26+97);
		
		int v=getfail(now,i);
		if(!t[v][s[i]-'a']){
			fail[++tot]=t[getfail(fail[v],i)][s[i]-'a'];
			t[v][s[i]-'a']=tot;
			len[tot]=len[v]+2;
			num[tot]=num[fail[tot]]+1;
		}
		now=t[v][s[i]-'a'];
		lastans=num[now];
		cout<<lastans<<' ';
	}
	cout<<endl;
	
	return 0;
}

后缀数组

定义

我们需要先定义两个数组：

$sa_i$ 表示后缀排序之后第 $i$ 小后缀的编号。这个就是后缀数组。
$rk_i$ 表示后缀 $i$ 的排名。

性质： $sa_{rk_i} = rk_{sa_i} = i$ 。

求法

我们需要利用倍增的思想，就是对于长度为 $2^k$ 的子串进行排序处理， $k=1,2,3,\cdots$ 。

然后这个倍增很妙，就是利用这个子串的前一半作为第一关键字，第二半作为第二关键字，进行排序。

复杂度 $O(n\log^2 n)$ 。桶排序可以做到单 $\log$ 。

height

$lcp(i,j)$ 表示 $i,j$ 这两个后缀的最长公共前缀。

height_i = lcp(sa_i,sa_{i-1})

其中 $h_1=0$ 。

h_{rk_i}\ge h_{rk_{i-1}}-1

$height$ 数组可以根据这个暴力求。

性质：

LCP(p, q) = \min\{ h_{rk_{p}+1}, h_{rk_{p}+2}, ..., h_{rk_{q}} \}

注意： $k$ 个数有 $k-1$ 个 height。

P2178 [NOI2015] 品酒大会

P2178 [NOI2015] 品酒大会。

第一个问题就是问有多少个 $i,j$ 使得 $lcp(i,j)\ge r$ 。

倒序枚举问题就转化成了有多少个 $lcp(i,j) = r$ 的了。然后这个我们可以用 $height$ 数组转化成 $\min \{h_{i+1},h_{i+2},\cdots,h_j\}$ （排序之后）。

然后问题可以转化成有多少 $i,j$ 满足这里面的 $height$ 的最小值恰好等于 $r$ 。

然后可以继续优化，按照 $height$ 数组降序排序插入，计算答案。计算方法就是当前这条“边”，然后两边的堆的个数相乘。

第二问我们只需要维护最大值就行了。不过有负数，所以最小值也需要维护上。

P4248 [AHOI2013] 差异

P4248 [AHOI2013] 差异。

还是跟上一道题一样，需要先转化成 $height$ 数组，然后利用性质：

lcp(p, q) = \min\{ h_{rk_{p}+1}, h_{rk_{p}+2}, ..., h_{rk_{q}} \}

然后问题就转化成了区间最小值的和了，用单调栈。

Lyndon 分解

P6114 【模板】Lyndon 分解。

引理 1：如果 $u$ 和 $v$ 都是 $\text{Lyndon}$ 串并且 $u<v$ ，则 $uv$ 也是 $\text{Lyndon}$ 串。

如果 $len(u)\ge len_v$ 就易证了，因为 $v$ 在 $len$ 后面的一定比 $uv$ 小。

否则，如果 $u$ 不是 $v$ 前缀，易证，是的话，如果 $v<uv$ 那么 $v[len(u)+1]...<v$ ，矛盾。

唯一性

存在性

$A_i=S[i]$ ，然后每次不断找到 $A_i<A_{i+1}$ 并且合并为一个串，最后一定能使得所有的 $A_i\ge A_{i+1}$ 。

唯一性

（不想写了，直接看题解的吧）

假设对于字符串 $S$ 存在两个 $\text{Lyndon}$ 分解：

$S=A_1A_2\cdots A_iA_{i+1}A_{i+2}\cdots A_{m_1}$

$S=A_1A_2\cdots A_iA^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{m_1}$

设 $\operatorname{len}(A_{i+1})>\operatorname{len}(A^\prime_{i+1})$ 。

观察 $A_{i+1}$ 在第二种分解中的对应情况。假设 $A_{i+1}=A^\prime_{i+1}A^\prime_{i+2}\cdots A^\prime_{k}A^\prime_{k+1}[:l]$ 。

那么由 $\text{Lyndon}$ 串的性质可知：

$A_{i+1}<A^\prime_{k+1}[:l]\le A^\prime_{k+1}\le A^\prime_{i+1}<A_{i+1}$

矛盾。

引理2：若字符串 $v$ 和字符 $c$ 满足 $vc$ 是某个 $\text{Lyndon}$ 串的前缀，则对于字符 $d>c$ 有 $vd$ 是 $\text{Lyndon}$ 串。

这个可以感性理解。

Duval 算法

这个算法的本质就是维护一个周期串。

维护 $i,j,k$ ， $1$ 到 $i$ 已经固定，现在在 $k$ ， $k-j$ 就是一个周期的长度。

$s_k=s_j$ 的时候周期保持。

$s_k>s_j$ 的时候根据引理 $2$ ，我们可以形成一个新的 Lyndon 串。然后这个点重新作为周期，因为多余的这一块可以证明是能合并的，然后引理 $1$ 告诉我们这个也可以跟前面合并。

$s_k<s_j$ ，我们直接右移 $i$ 就行了。