学习笔记——KMP字符串匹配算法
@[toc]
简介
KMP算法是一种字符串匹配算法，它利用了模式串（被匹配串）自身的相关信息来减少匹配次数。本文假设文本串（待匹配串）为T，模式串（被匹配串）为P。而T，P的长度分别为TLen，PLen。记T~i~为T的前i个字符构成的子串，T~-i~为T后i个字符构成的子串，P同理。
求辅助数组
在实现这个算法前，我们需要先求一个特殊的数组，暂且记为Pre[PLen+1]。这个数组的含义为Pre[i]=max(j),其中记H=P~i~，其中j满足(j<=i&&H~j~=H~-j~)，即P~i~的最长的（前缀等于后缀）的长度。我们暂且把为什么要这个放在一边，先看看怎么求。首先，先上代码。
1 | template<typename Ty> |
代码中的表示当前匹配成功了看个长度，我们先看代码中的while循环，此时已经匹配到了第q项，即对应上图中的的i项，其中前i-1项已经匹配完成，准备匹配第i项，那此时的max（j）怎么求呢？此时的k为上一项的max=（j），即i-1时的max（j），记为k~0~,那如果P[k~0~+1]==P[i],那第i项的max（j）等于第i-1项的max（j）+1，所以直接退出循环，然后触发if，Pre[i]=k~0~++。如果P[k~0~+1]!=P[i]，那就直接找前k~0~项中最大的max(j)，记为k~1~，即k~1~=Pre[k~0~]，然后再判断P[k~1~+1]和P[i]是否相等，一直找到P[k~n~+1]=P[i]为止，或者是循环到Pre[1]，那此时k自然为0然后进入if判断，一直往复循环，最终更新完Pre数组为止。
时间复杂度
这里时间复杂度的分析方法采用聚合分析的方法。首先，k初始化为0，不难发现，k的递增只能来源于for循环中的if语句，且假设每次都递增的话，k至多递增PLen-1次（for循环次数），而k的减少只能来源与while循环，所以while循环至多执行PLen-1次，所以时间复杂度为$O(PLen)$。
关于辅助数组的两道题
ProblemD Power Strings
假设s可以由t重复k次拼成，即s=tttt……tt，我们称为s=t^k^。先给定一个字符串s，求最大的n使得存在t满足s=t^n^。
Input
多组数据，每行一个字符串(仅包含可打印字符且长度不超过1000000)，以单独一行.作为终结标志
Output
每组数据一行答案
Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3
Hint：This problem has huge input, use scanf instead of cin to avoid time limit exceed.定理：假设P的长度为PLen，则P存在循环子串，当且仅当，len可以被Plen - Pre[Plen]整除，最短循环子串为S[PLen - Pre[PLen]]
例子证明：
设P=q~1~q~2~q~3~q~4~q~5~q~6~q~7~q~8~，并设Pre[8] = 6，此时str = P[PLen - Pre[len]] = q~1~q~2~，由字符串辅助数组Pre的定义可知，q~1~q~2~q~3~q~4~q~5~q~6~ = q~3~q~4~q~5~q~6~q~7~q~8~，即有q~1~q~2~＝q~3~q~4~，q~3~q~4~＝q~5~q~6~，q~5~q~6~＝q~7~q~8~，即q~1~q~2~为循环子串，且易知为最短循环子串。由以上过程可知，若PLen可以被PLen - Pre[PLen]整除，P存在循环子串，否则不存在。
引用至(https://www.cnblogs.com/zyx1314/p/3615651.html）
所以直接看最短循环字串长度能否被PLen整除即可。1
2
3
4
5
6
7
8
9template<typename Ty>
inline void KMP<Ty>::ProblemD(){
ComputePrefixFunction();
int Len = PLen - Pre[PLen];
if (PLen%Len)
cout << 1 << endl;
else
cout << PLen / Len << endl;
}
ProblemE Seek the Name, Seek the Fame
给定一个字符串s，从小到大输出s中既是前缀又是后缀的子串的长度。即输出所有k满足s[0..k-1]=s[l-k,l-1] (l为s长度)
Input
多组数据，每组一行一个字符串(仅出现小写字母且长度不超过400000)
Output
对于每组数据。从小到大输出一行所有满足条件的k。
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
设图中黑线为文本串，灰线为Pre[PLen]的情况，即原串的最长前后缀，符合题意，然后暗红串为Pre[Pre[PLen]]，根据Pre定义，前两条暗红线相同，因为灰串部分左右相同，所以第二条暗红线等于第三条，所以第一条等于第三条，所以暗红线符合题设，亮红线同理，就这样推到底就行了。注意最后输出本身长度。。。
1 | template<typename Ty> |
字符串匹配
那么，获取了辅助数组后，我们怎么更高效的进行匹配呢？
此图来自算法导论的某一页233333.看图a中的，当前匹配项失配了，然后我们发现T中灰色部分的后三项aba在上一次匹配中已经确定和P灰色部分的后三项aba匹配，然后根据Pre数组的
定义，P的前三项等于后三项，所以已经此时匹配时已经确定了P的灰色前三项和T的灰色后三项匹配，无需重复匹配，并且Pre[当前位置]=3确定了而不是4确定了P偏移一格是无效的（图中的讲解要看看）换成代码就是
整个代码和ComputePrefixFunction()思想时一样的1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20template<typename Ty>
inline void KMP<Ty>::ProblemG() {
ComputePrefixFunction();
int q = 0;
for (int i = 1; i <= TLen; i++) {
while (q > 0 && P[q + 1] != T[i]) {//其实和求辅助数组时的while原理类似
q = Pre[q];
}
if (P[q + 1] == T[i]) {
q++;
}
if (q == PLen) {
cout << i - PLen + 1 << endl;
q = Pre[q];//如果要找多个不直接return的话要加这一步
return;
}
}
cout << -1 << endl;//表示找不到
return;
}
然后有个模板Hduoj1711
时间复杂度
类似的思想，类似的聚合分析，看q的增减情况可知时间复杂度为$O(TLen)$
ProblemH Censor
现在给定一个你很讨厌的字符串 A 和另外一个字符串 B，请删除在 B 中出现的所有 A。
请注意：有可能在删除一个 A 后导致新的 A 出现，此时请继续删除，直到没有 A。输入格式
输入为多组数据，请处理到 EOF。
对于每组数据：
第一行为你很讨厌的字符串 A，第二行为另外一个字符串 B，均仅包括小写字母。
保证 A串 和 B串 的长度不超过 5000000 且 A、B 均不为空串。输出格式
对于每组数据，输出一行，即完成删除后的字符串。样例输入
abc
aaabcbc
b
bbb
abc
ab
样例输出
a
</br>
ab
样例解释
第一组数据的删除过程：
aaabcbc -> aa[abc]bc -> aabc -> a[abc] -> a
第二组数据的删除过程：
bbb -> [b]bb -> bb -> [b]b -> b -> [b] ->
第三组数据由于讨厌的字符串并没有出现，所以没有被删除任何一个部分。
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29template<typename Ty>
inline void KMP<Ty>::ProblemH() {
ComputePrefixFunction();
int cnt = 1;//ans的坐标，初始化为1
char*ans= new char[TLen + 2];//记录答案
int*Pos = new int[TLen + 5];//记录当前位置匹配的长度
int q = 0;
Pos[0] = 0;
for (int i = 1; i <= TLen; i++, cnt++) {
ans[cnt] = T[i];//和文本串进行拷贝
while (q > 0 && T[i] != P[q + 1]) {//while和下面的if为KMP匹配的过程
q = Pre[q];
}
if (T[i] == P[q + 1]) {
q++;
}
Pos[cnt] = q;//记录当前坐标匹配成功的长度
if (q == PLen) {//如果此时和模式串匹配成功（令人讨厌的串）
cnt -= PLen;//坐标直接左移PLen格，相当于删除操作
q = Pos[cnt];//q=删除的串的左端已经匹配成功的个数
}
}
for (int i = 1; i <= cnt - 1; i++) {//输出答案
cout << ans[i];
}
cout << endl;
delete[]ans;
delete[]Pos;
}
最后来个全家福嘻嘻嘻
1 |
|
End
