【算法】字符串

参考资料

算法学习笔记：KMP算法
算法学习笔记：Manacher算法
常见字符串算法

一、Trie

1. 概念

理论上来说是一种存储字符串的数据结构，将每个节点看做一个字符，一条有效的路径存储的便是一整个单词。

Trie 常用于求一个单词是否出现过、几个单词的最长公共前缀等。

2. 实现

当然，一个单词的开头可以是 a 到 z 的任意字符（当然也可以是大写），如果这样存储最后形成的是森林而不是树。为了方便起见，我们常用一个虚根来连接它们。

然后考虑空间复杂度，不难想到，如果不考虑任何优化的前提下，每一层就需要 \(26^k\) 个节点（\(k\) 为深度），这样的空间复杂度显然是不行的。这里可以用动态开点来维护，\(nex_{[x][i]}\) 数组表示节点编号为 \(x\) 的第 \(i\) 个孩子的编号，如果为 \(0\) 说明以前没有访问过，就将其赋值为当前已用编号加一。

于是空间复杂度降低到了 \(n\times l\) 级别的（\(n\) 是字符串个数，\(l\) 是最长的字符串长度）。

举个例子：

现在有几个字符串：biuld、ak、ioi、boom。

先将 biuld 放入树中（为区分不同单词相同字母，下划线后的数字表示它在树中的编号）

再插入 ak 和 ioi，过程和放入 biuld 的差不多。

最后放入 boom，由于第一位的 b 之前已经访问过了，所以后面的 oom 和 iuld 公用同一个父节点。

3. 代码

模板

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,m;
int nex[N][30],cnt;
//nex表示下一个孩子的编号
//cnt是已经存储的编号
bool vis[N],las[N];
//vis是针对与这道题目的，表示以前是否访问过
//las表示该节点是不是单词的末尾

void update(string &s){//&代表只读取这个字符串，但不更改
	int now=0;
	for(int i=0;i<s.size();i++){
		int tmp=s[i]-'a';
		if(nex[now][tmp]==0) nex[now][tmp]=++cnt;//如果以前没访问过就要增点
		now=nex[now][tmp];//访问它的儿子
	}
	las[now]=true;//这个节点就是单词末尾
}

int query(string &s){
//return 0：存在这个单词，并且以前没有访问过
//return 1：不存在这个单词
//return 2：存在这个单词，但以前访问过
	int now=0;
	for(int i=0;i<s.size();i++){
		int tmp=s[i]-'a';
		if(nex[now][tmp]==0) return 1;//还没有这个节点，表示根本就没这个单词
		now=nex[now][tmp];
	}
	if(las[now]==false) return 1;//不是单词，但是已出现的单词的一个前缀
	else if(vis[now]==false){
		vis[now]=true;
		return 0;
	}
	return 2;
}

int main(){
//	freopen("1.in","r",stdin); 
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		update(s);
	}
	return 0;
}

二、MP（KMP）

1. 概念

KMP 算法常用于匹配两个字符串，如字符串 t 在字符串 s 中所有的出现位置。不过 KMP 中匹配的思想很重要。现在一般常用的都是 \(mp\) 算法，\(kmp\) 算法实际上还有一个优化，先挖着坑。

2. 实现

对于暴力求出现位置的思路，我们不难想到枚举在 s 中每一个长度等于 t 字符串的长度，判断是否相等即可。

而这样一位一位的判断过去，会有很明显不成立的情况（比如 t 的第一位是 a，但现在循环到的位置是 b、c等），这样会很浪费时间。我们可以考虑一个数组来维护与其相等的位置。

现在有一串字符串 \(s\)，设 \(fail_{[i]}=k\) 表示 \((s_{[0...k-1]})\) 与 \((s_{[i-k+1...i]})\) 相等。于是当失配时，将指向需要寻找的字符串的指针 \(j\) 变为 \(fail_{[j-1]}\)。

由于前 \(k\) 个和后 \(k\) 个已经匹配，也就是相同了，那么这样移动指针可以确保在这个失配位置之前的字符串都是匹配的。

样例解释一下:

(下标从 \(0\) 开始)

这时候红色的部分失配了，我们将指向下面的指针 \(j=5\) 变成 \(j=fail_{[4]}=1\)，此时指向上面字符串的指针 \(i\) 依旧为 5。移动指针后两个字符匹配。

这时候我们找到了匹配的字符串。

代码实现如下：

void fin(string &s,string &t){
	int x=0;//x与j同意义
	for(int i=0;i<s.size();i++){
		while(x!=0&&t[x]!=s[i]) x=fail[x-1];
		if(t[x]==s[i]) x++;//匹配成功了就匹配下一位
		if(x==t.size()){
			//找到了匹配的字符串位置，进行输出操作等（如P3375）
			x=fail[x-1];
		}
	}
}

在预处理 \(fail\) 数组的时候，我们可以将整个字符串向右移一个位置，再进行匹配。

如果匹配上了，那么 \(fail_{[i]}=j\)（按照 \(fail\) 数组的定义），否则像之前匹配一样，\(j=fail_{[j-1]}\)，再继续匹配。

void kmp(string &s){
	int x=0;
	for(int i=1;i<s.size();i++){
		while(x!=0&&s[x]!=s[i]) x=fail[x-1];
		if(s[x]==s[i]) x++;
		fail[i]=x;
	}
}

3. 代码

模板

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int fail[N];

void kmp(string &s){
	int x=0;
	for(int i=1;i<s.size();i++){
		while(x!=0&&s[x]!=s[i]) x=fail[x-1];
		if(s[x]==s[i]) x++;
		fail[i]=x;
	}
}

void fin(string &s,string &t){
	int x=0;
	for(int i=0;i<s.size();i++){
		while(x!=0&&t[x]!=s[i]) x=fail[x-1];
		if(t[x]==s[i]) x++;
		if(x==t.size()){
			cout<<i-x+2<<"\n";
			x=fail[x-1];
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	string s,t;
	cin>>s>>t;
	kmp(t);
	fin(s,t);
	for(int i=0;i<t.size();i++) cout<<fail[i]<<" ";
	return 0;
}

三、Manacher

1. 概念

Manacher（马拉车）用于 \(O(n)\) 求出回文串长度。

2. 实现

对于一个回文串，它有可能是奇回文串（左）或者偶回文串（右），红色部分是回文串的中心。

对于一个奇回文串，它是比较好求的，只需要找到中心然后向两边扩展判断即可。那么我们也同样可以将偶回文串看做是两个中心部分间的空（如上图，也就是两个 b 之间的缝隙）。我们一般用一些不会再题目给出的字符串类型来填空，如 #、$、&等（具体需要看题目要求）。

为了懒得处理数组越界的情况，可以在字符串最左端和最右端填入两个不同的字符。

//处理回文中心
void pre(){
	string t;
	cin>>t;
	s[0]='!';s[++n]='#';
	for(int i=0;i<t.size();i++){
		s[++n]=t[i];
		s[++n]='#';
	}
	s[++n]='%';
}

定义一个数组 \(d_{[i]}\) 表示以 \(s_{[i]}\) 为回文中心的最长回文半径，同时维护 \(mid,r\) 表示 \(s_{[2mid-r...r]}\) 是满足 \(mid\le i\) 且 \(r\) 值最大的回文串（当然你也可以维护 \(l,r\) 表示区间左、右端点）。

如果 \(i>r\)，这时候没有好的转移方式，直接暴力求解 \(d_{[i]}\)。

if(i>r){
	d[i]=1;//自己本身就是一个回文串
	while(s[i+d[i]]==s[i-d[i]]) d[i]++;
}

如果 \(i\le r\)，那么表示 \(i\) 还在一个回文串中。找到在这个回文串中与 \(i\) 对称的点，根据中点公式推出对称的点 \(j=2\cdot mid-i\)。

如果以 \(s_{[j]}\) 为中心的回文串左端点在整个大的回文串（也就是以 \(r\) 为右端点，\(mid\) 为中心的那个）内，那么根据回文串的对称性得： \(d_{[i]}=d_{[j]}\)

如果超出了这个大的回文串，表示以 \(s_{[j]}\) 为中心的回文串半径一定超过了 \(j-l+1\)（\(l=2mid-r\)），之后暴力更新即可。

最后更新一下 \(r\) 的最大值。

void manacher(){
	int mid=0,r=0;//初始没有回文串
	for(int i=1;i<n;i++){
		if(i<=r){
			d[i]=min(d[mid*2-i],r-i+1);
			//令j=mid*2-i
			//由于如果以mid为中心的回文串包含以j为中心的回文串，那么d[j]一定会小于它到最左端的距离=j-l+1=r-i+1
		}
		else d[i]=1;
		while(s[i+d[i]]==s[i-d[i]]) d[i]++;//暴力更新
		if(i+d[i]-1>r) r=i+d[i]-1,mid=i;//更新r
	}
}

3. 代码

模板

#include<bits/stdc++.h>
using namespace std;
const int N=3e7+5;
int n;
int d[N];
char s[N];

void manacher(){
	int mid=0,r=0;
	for(int i=1;i<n;i++){
		if(i<=r)
			d[i]=min(d[mid*2-i],r-i+1);
		else d[i]=1;
		while(s[i+d[i]]==s[i-d[i]]) d[i]++;
		if(i+d[i]-1>r) r=i+d[i]-1,mid=i;
	}
}

int main(){
	ios::sync_with_stdio(false);
	string t;
	cin>>t;
	s[0]='!';s[++n]='#';
	for(int i=0;i<t.size();i++){
		s[++n]=t[i];
		s[++n]='#';
	}
	s[++n]='%';
	manacher();
	int ansi=0;
	for(int i=1;i<n;i++) ansi=max(ansi,d[i]-1);
	//由于d[i]是包含占位符的回文半径
	//所以真正的回文串长度=(d[i]-1)/2*2
	cout<<ansi;
	return 0;
}