字符串相关 学习笔记

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

哈希和哈希表

令 \(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\)。