KMP/扩展KMP学习笔记
# 前言
突然发现自己kmp算法掌握得不是很到位。写一篇笔记就当复习好了。
# KMP
指向的是当前位失配时,与模式串前缀相同的最长后缀,也是下一次配对的位置
举个例子,当计算指针时,假设模式串为"ababc"
则
一个容易理解的算法,并不需要太多解析。
# 模板
#include <bits/stdc++.h>
using namespace std;
char ori[1000050], pattern[1000050];
int f[1000050], l1, l2;
void calc(){
int k=0;
f[0]=f[1]=0;
for(int i=1; i<l2; i++) {
while(k && pattern[i]!=pattern[k]) k=f[k];
//无下面这一行代码则应称为MP算法
while(k && pattern[i+1]==pattern[k]) k=fail[k];
f[i+1]= pattern[i]==pattern[k]?++k:0;
}
}
int main() {
scanf("%s", ori);
scanf("%s", pattern);
l1 = strlen(ori);
l2 = strlen(pattern);
calc();
int k=0, i=0;
while(i<l1){
if(ori[i]==pattern[k]){
i++, k++;
if(k==l2){//匹配完成,匹配下一段字符串
printf("%d\n", i-k+1);
i=i-f[k];//f[k]等于 当第k位字符不匹配时,"前面已匹配字符串"的长度
k=f[k];
}
}else{
if(!k)i++;//连第一位都匹配失败,i移向下一位
else{
k=f[k];//跳转
}
}
}
}
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
29
30
31
32
33
34
35
36
37
38
39
40
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
29
30
31
32
33
34
35
36
37
38
39
40
# 扩展KMP
典型问题:给定串,对于的每一个后缀,求与的最长公共前缀。
# z函数
对于一个长度为的字符串(下标从0开始),定义其z函数,为与的最大公共前缀长度。
显然有
例如:
其朴素算法如下
void calc_z_func(int * z, char * s, int len){
for(int i=1; i<len; i++){
z[i] = 0;
while(i + z[i] < len && s[z[i]] == s[z[i] + i]) z[i]++;
}
}
1
2
3
4
5
6
2
3
4
5
6
# 利用z[1]...z[i-1]计算z[i]
定义匹配段为 与的某一前缀相同的 的子串。例如,则("aa")为一个匹配段。
在计算到的过程中,我们记下最右(右边界最大的)的匹配段,该视为算法目前扫描到的边界,任何超过的字符都是未扫描的。
下面分情况讨论:
,由于当前位置处于未扫描的部分,因此使用朴素算法进行扫描匹配即可。
:
注意到,因此有。因此,我们可以利用作为参考。注意到可能超过,而超过的部分都是未扫描的。因此有
接下来继续使用朴素算法去求就行。
void calc_z_func(int * z, char * s, int len){
z[0] = len;
for(int i=1, l=0, r=0; i<n; i++){
z[i] = 0;
if(i <= r) z[i] = min(r - i + 1, z[i-l]);
while(i + z[i] < len && s[z[i]] == s[z[i] + i]) z[i]++;
if(i + z[i] - i > r) l = i, r = i + z[i] - 1;
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
注意:如果从开始,会使得最右匹配段一直为,算法退化为
# 求s每个后缀与t的最长公共前缀
在求出上述函数后,仿照函数的求法即可。
即为后缀与的最长公共前缀
int len_s = strlen(s), len_p = strlen(p);
calc_z_func(p, len_p);
for(int i=0, l = -1, r = -1; i<len_s; i++){
extend[i] = 0;
if(r >= i) extend[i] = min(r - i + 1, z[i - l]);
while(i + extend[i] < len_s &&
s[i + extend[i]] == p[extend[i]])
extend[i]++;
if(extend[i] + i - 1 > r) r = extend[i] + i - 1, l = i;
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 其他应用
# 查找子串
问题:求串在串中出现的位置
解法:
令,其中为中均为出现过的字符。
计算函数,对于,若,则有一个出现在的第号位置。
# 参考链接
我自己的博文:https://blog.csdn.net/Chgtaxihe/article/details/88919673
https://oi-wiki.org/string/z-func/
上次更新: 2021/02/24, 03:37:30