有一个主串S = {a, b, c, a, c, a, b, d, c}, 模式串T = {a,b,d} 式串在主串S中第一次出现的位置;
提示: 不需要考虑字符串大小写问题, 字符均为小写字母。
KMP算法核心：KMP算法的时间复杂度O(m+n)。
尽量减少模式串T与主串S的匹配次数以达到快速匹配的目的。主要是通过一个next()函数实现，函数本身包含了模式串T的局部匹配信息以及求得next数组的规律，next数组表示的是一次遍历匹配失败后，模式串T的下标j 该移动到第几位，然后再进行下一次遍历匹配。
KMP算法探索（PS：图中i 与 j 的初始值 均从1 开始）
在BF算法解决字符串匹配时，主串S和模式串T中某个字符不相等时，S串需要回退到之前对比过的字符的下一个字符位置 i，T串需要继续回退到 j = 1的位置，进行下一次遍历匹配对比，如此循环，这个过程主串S可能需要回退很多遍，这导致其时间复杂度到了O(n*m)。
1、BF算法中不必要的对比发现** — 可减少主串S的index回溯
BF模拟1!
接下来开始主串S和 模式串T的index 回溯对比
BF模拟2，3，4，5，6
操作①中，前5个字母S&T中都相等，T串首字母“a”与后续字母均不相同，可知“a”不与S中2-5的字母相同。以下：
不相等
所以，后续的2 3 4 5的对比很多余，只保留①与⑥的对比即可。
BF算法中不必要的对比发现
这些不必要的对比，不必要的index 回溯，正式KMP算法规避的，也是KMP算法核心之一，算法如此哦。
2、前缀=后缀的发现，可以使T串中 j 回溯到 j = 3 的位置。** — 减少回溯
前缀后缀的发现
没有相等的前缀后缀
T串首字符串前缀与自身后边的字符后缀比较，若相等，则j 的值可以变化 减少回溯。
因此得出以下规律：
T串遍历， j 回溯规律
3、next数组值推导**
case1：模式串中无任何重复字符
next数组值
case2: 模式串“abcabx” 包含重复的前后缀“a” 和 "ab"
前后缀“a” 和 "ab"
case3: 模式串“aaaaaaab "
模式串“aaaaaaab "
得出经验结论：如果前缀后缀有一个字符相等，回溯值k = 2, 2个字符相等k = 3, n个相等 则k = n+1;
也就是说，next数组里面存放的是要查找的字符串前i个字符串的所有前缀、后缀相等的公共串(多个，“a” "ab")中，公共串的最大的长度值
4、next数组代码实现
思路：
1：遍历模式串T，next数组默认next[1] = 0;
2：需要i, j ，i表示前缀下标，j 后缀下表，i = 0时，从头开始对比，i++，j++,则next[j] = i;
3：当T[I] == T[j]时，表示有前后缀字符相等，则i++ j++,next[j] = i;
4：当T[I] != T[j]时，i需要回退到合理位置，i = next[i];
void get_next(String T,int *next){
int i = 0;
int j = 1;
next[1] = 0;
//printf("length = %d\n",T[0]);
while (j < T[0]) {//T[0]为模式串T的长度
//printf("i = %d j = %d\n",i,j);
if(i ==0 || T[i] == T[j]){
//考虑 T = a b c a b x
//next = [0,1,1,1,2,3]
++i; //T[i] 表示前缀的单个字符;
++j; //T[j] 表示后缀的单个字符;
next[j] = I;
printf("next[%d]=%d\n",j,next[j]);
}else {
i = next[i];//如果字符不相同,则i值回溯;
}
}
}
//KMP 匹配算法(1)
//返回子串T在主串S中第pos个字符之后的位置, 如不存在则返回0;
int Index_KMP(String S,String T,int pos){
//i 是主串当前位置的下标准,j是模式串当前位置的下标准
int i = pos;
int j = 1;
//定义一个空的next数组;
int next[MAXSIZE];
//对T串进行分析,得到next数组;
get_next(T, next);
count = 0;
//注意: T[0] 和 S[0] 存储的是字符串T与字符串S的长度;
//若i小于S长度并且j小于T的长度是循环继续;
while (i <= S[0] && j <= T[0]) {
//如果两字母相等则继续,并且j++,i++
if(j == 0 || S[i] == T[j]){
I++;
j++;
}else{
//如果不匹配时,j回退到合适的位置,i值不变;
j = next[j];
}
}
if (j > T[0]) {
return i-T[0];
}else{
return -1;
}
}
KMP算法next数组获取优化
当S = "aaaabcde" T = "aaaaax"时，next = [0,1,2,3,4,5],初次遍历到 x 时，I = 5，j = 5, next[5] = 4, j 回溯到 j = 4 为“a”, I = 5 为b ，对比不相等，继续的话按照next[j-1] 再对比依然不匹配，对比操作多余了，可优化。为了节省对比，需要next = [0,0,0,0,0,5]
解读一下示例：
优化next数组
优化解析
思路：
在求解nextVal数组的5种情况:
- 默认nextval[1] = 0;
- T[i] == T[j] 且++i,++j 后 T[i] 依旧等于 T[j] 则 nextval[i] = nextval[j]
- i = 0, 表示从头开始i++,j++后,且T[i] != T[j] 则nextVal = j;
- T[i] == T[j] 且++i,++j 后 T[i] != T[j] ,则nextVal = j;
- 当 T[i] != T[j] 表示不相等,则需要将i 退回到合理的位置. 则 i = next[i];
void get_next(String T,int *next) {
int i = 0;
int j = 1;
next[1] = 0;
while (j < T[0]) {
if (i == 0 || T[i] == T[j]) {
i++;
j++;
if (T[i] != T[j]) {//如果当前字符与前缀不同,则当前的j为next 在i的位置的值
next[j] = i;
} else {//如果当前字符与前缀相同,则将前缀的next值 值赋值给next[j] 在i的位置
next[j] = next[i];
}
} else {
i = next[i];//如果字符不相同,则i值回溯;
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, KMP匹配算法实现!\n");
int i,*p,*t;
String s1,s2;
int Status;
/*关于next数组的求解*/
StrAssign(s1,"aaaaax");
printf("子串为: ");
StrPrint(s1);
i=StrLength(s1);
p=(int*)malloc((i+1)*sizeof(int));
get_next(s1,p);
printf("Next为: ");
NextPrint(p,StrLength(s1));
t=(int*)malloc((i+1)*sizeof(int));
get_nextVal(s1, t);
printf("NextVal为: ");
NextPrint(t,StrLength(s1));
printf("\n");
//KMP算法调用
StrAssign(s1,"abcababca");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcdex");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,0);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"abccabcceabc");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"abcce");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,-2);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
StrAssign(s1,"aaaabcde");
printf("主串为: ");
StrPrint(s1);
StrAssign(s2,"aaaaax");
printf("子串为: ");
StrPrint(s2);
Status = Index_KMP(s1,s2,1);
printf("主串和子串在第%d个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配] \n",Status);
Status = Index_KMP(s1, s2, 1);
printf("主串和子串在第%d个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配] \n\n",Status);
return 0;
}
// 打印
Hello, KMP匹配算法实现!
子串为: aaaaax
next[2]=1
next[3]=2
next[4]=3
next[5]=4
next[6]=5
Next为: 012345
NextVal为: 000005
主串为: abcababca
子串为: abcdex
next[2]=1
next[3]=1
next[4]=1
next[5]=1
next[6]=1
主串和子串在第-1个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第-1个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
主串为: abccabcceabc
子串为: abcce
next[2]=1
next[3]=1
next[4]=1
next[5]=1
主串和子串在第5个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第5个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
主串为: aaaabcde
子串为: aaaaax
next[2]=1
next[3]=2
next[4]=3
next[5]=4
next[6]=5
主串和子串在第-1个字符处首次匹配（KMP算法）[返回位置为负数表示没有匹配]
主串和子串在第-1个字符处首次匹配（KMP_2算法）[返回位置为负数表示没有匹配]
网友评论