字符串相关 学习笔记

发表于 更新于
比较全面的提高级字符串知识

哈希和哈希表

令 $b$ 为选取的基数（229或233等），则字符串匹配时子串 $C’=c_{k+1}c_{k+2}\dots c_{k_n}$ 的哈希值为
$$ H(C’)=H(C,k+n)-H(C,k)\times b^n $$

哈希的相关运用

  • 哈希字符串匹配

转化成上面的板子就好做了。

  • 哈希找回文串

正着存一组哈希值，再倒着存一组哈希值。枚举回文串的对称中心，二分回文长度（的一半），利用哈希判等。可以在 $O(n\log n)$ 的复杂度内找最长的回文串、回文串的数量。

例题：P3501

KMP

运用两个指针 $i,j$ 表示以 $A[i]$ 结尾长度为 $j$ 的字符串正好与 $B$ 串的前 $j$ 个字符匹配。若下一个字符匹配，则挪动指针；否则将 $j$ 挪动到 $fail[j]$ 处。 $fail[j]$ 为失配数组，表示在 $B$ 串的 $j$ 处失配时， $j$ 应该往前跳到的位置。

首先对 $B$ 串预处理，得到 $fail$ 数组，预处理过程可视为 $B$ 串自己和自己匹配的过程。

该算法复杂度为线性的。

KMP的相关运用

  • KMP求公共前后缀

在KMP中，若一个串长度为 $n$ ，则 $fail[n]$ 就是该串公共前后缀的长度。

  • KMP求最大（最小）周期

如果一个长度为 $n$ 的串有长度为 $j$ 的公共前后缀，则该串必有长度为 $n-j$ 的周期。

由此，在KMP中，若一个串长度为 $n$ ，则 $fail[n]$ 是最长公共前后缀，则 $n-fail[n]$ 是该串的最小周期；在 $j>0$ 时找 $fail[j]$ ，最小的非0的 $j’$ 是最短公共前后缀，则 $n-j’$ 是该串的最大周期。

扩展KMP

求解的问题：求出一个字符串的每个后缀与一个字符串（可以是自己）的最长公共前缀。

先暴力求得 $Z_1$ 的值，然后向后枚举。像后文的 manacher 一样维护 $pos,maxr$，并判断 $Z_{i-pos}$ 能否扩展到 $maxr$ 右边，如果不能就直接更新 $Z_i$，否则暴力更新。

失配树

求解的问题：求出一个字符串的两个前缀的最长公共前后缀。

先跑KMP，容易发现，一个字符串的最长公共前后缀就是 $fail[n]$。同时 $fail[fail[n]]…$ 等都是他的最长公共前后缀。那么我们容易知道，两个字符串的公共前后缀构成树形。于是我们将 $(fail[i],i)$ 连边，会得到一棵树，这就是失配树。上面那个问题可以在失配树上求LCA解决。

AC自动机

若有一个主串需要与多个模式串匹配，需要用的AC自动机。考虑将多个模式串建立字典树，再在字典树上建立 $fail$ 数组，即可完成匹配。

具体实现：先建立字典树，注意下标从1开始。然后将0号结点的所有边全部连向1号结点。从1开始进行广搜，对于每个结点 $u$，枚举所有出边，若不存在，则直接将出边连向 $fail[u]$ 的出边；否则将儿子入队，找到 $fail[u]$ 能跳到的有和该儿子相同的结点，更新 $fail[v]$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void init(){
	for(int i=0;i<26;i++)tr[0][i]=1;
	queue<int> q;
	fail[1]=0;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(!tr[u][i])tr[u][i]=tr[fail[u]][i];
			else{
				q.push(tr[u][i]);
				int v=fail[u];
				while(v>1&&!tr[v][i])v=fail[v];
				fail[tr[u][i]]=tr[v][i];
			}
		}
	}
}

AC自动机相关题目处理技巧

可以先考虑只有一个模式串的情况，先按KMP的做法写，思路厘清后再甩到字典树上。

最小表示法

参考这个。思路和代码都比较简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int solve(){//返回最小表示的初始位置
	int i=1,j=2,k=0;
	while(i<=n&&j<=n&&k<n){
		if(num[i+k]==num[j+k]){
			k++;
			continue;
		}
		if(num[i+k]>num[j+k])i=i+k+1;
		else j=j+k+1;
		if(i==j)j++;
		k=0;
	}
	return min(i,j);
}

manacher算法

先在两个字符间插入一个特殊字符，然后执行以下步骤：

1.如果 $i<maxr_i$，按对称方法更新 $p_i$。

2.暴力拓展 $p_i$。

3.更新 $maxr$ 和 $pos$。