KMP介绍
KMP算法是一种改进的字符串匹配算法。
KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数。
KMP与BF不一样的地方是，主串的 i 不会回退，模式串的 j 也不会直接移动到0位置
j回到下标2的位置就很合适
目的：i不回退，j回退到合适的位置
因为i不回退，所以我们尽量在主串中找到与模式串匹配的一部分串
假设我们找到了（i能和j匹配到这里，说明前面有一部分匹配成功），绿色框的两个相同，又0…1和3…4相同，所以橙色的两个相同
p[0]…p[1] 和 p[3]…p[4]长度相同且为2，那么 j 就回退到2的位置
j 要移动的位置由next数组确定，next数组保存了模式串在某个位置匹配失败后，回退的位置
next[j]=k
k是 j 要移动的位置
k的值求法：
1.找到匹配成功部分的两个相等的真子串（不包含本身），一个以下标0开始，一个以下标 j -1结尾
2.next[0]=-1,next[1]=0
练习手求next数组：
那么已知next[i]=k,怎么求next[i+1]=？
假设 i 匹配失败后要回退到的位置是k
此时如果p[i]==p[k]
那么我们就可以知道i+1匹配失败后要回退的位置
如果p[i] != p[k]
k=next[k]继续回退，直到k= -1
如果回退到0下标后还是没有找到，k已经= -1了还是没有找到，那么next[i+1]=0
KMP代码
//str主串
//sub子串
//pos开始检查的开始位置
//str_len主串长度
//sub_len子串长度
int KMP(char* str, char* sub, int pos)
{
assert(str && sub);
int str_len = strlen(str);
int sub_len = strlen(sub);
if (str_len == 0 || sub_len == 0 || sub_len>str_len)
{
return -1;
}
if(pos<0 || pos>=str_len)
{
return -1;
}
int* next = (int*)malloc(sub_len * sizeof(int));
if (next == NULL)
{
perror("malloc");
return -1;
}
InitNext(sub, next, sub_len);//初始化子串的next数组
int i = pos;//遍历主串
int j = 0;//遍历子串
while (i < str_len && j < sub_len)
{
if (j==-1 || str[i] == sub[j])
{
i++;
j++;
}
else//j回退到next[j]
{
j = next[j];
//极端情况下：i
// a b c ...
// p b c ...
// j
//极端情况下：j刚开时和i就匹配不上，j = next[j];因为next[0]=-1,j=-1
}
}
free(next);
next=NULL;
if (j >= sub_len)
{
return i - j;
}
else
{
return -1;
}
}
next数组的初始化
next[0]= -1,next[1]=0，i=2，k=0
前面说到如果p[i]==p[k]
那么我们就可以知道i+1匹配失败后要回退的位置
这时候我们把i当成i+1，k当成k+1；想知道i匹配失败后回退的位置，就先求p[i-1]==p[k]成不成立
void InitNext(char* sub, int* next, int sub_len)
{
assert(sub && next);
next[0] = -1;
if(sub_len==1)
return;
next[1] = 0;
int i = 2;//代表当前位置的i
int k = 0;//代表前一项的k
while (i < sub_len)
{
if (k==-1 || sub[i - 1] == sub[k])
{
next[i] = k + 1;
i++;
k++;
}
else
{
k = next[k];//只要匹配不成功就回退，直到k= -1进行特殊处理
}
}
}
整体代码
void InitNext(char* sub, int* next, int sub_len)
{
assert(sub && next);
next[0] = -1;
if(sub_len==1)
return;
next[1] = 0;
int i = 2;//代表当前位置的i
int k = 0;//代表前一项的k
while (i < sub_len)
{
if (k==-1 || sub[i - 1] == sub[k])
{
next[i] = k + 1;
i++;
k++;
}
else
{
k = next[k];//只要匹配不成功就回退，直到k= -1进行特殊处理
}
}
}
//str主串
//sub子串
//pos开始检查的开始位置
//str_len主串长度
//sub_len子串长度
int KMP(char* str, char* sub, int pos)
{
assert(str && sub);
int str_len = strlen(str);
int sub_len = strlen(sub);
if (str_len == 0 || sub_len == 0 || sub_len>str_len)
{
return -1;
}
if(pos<0 || pos>=str_len)
{
return -1;
}
int* next = (int*)malloc(sub_len * sizeof(int));
if (next == NULL)
{
perror("malloc");
return -1;
}
InitNext(sub, next, sub_len);//初始化子串的next数组
int i = pos;//遍历主串
int j = 0;//遍历子串
while (i < str_len && j < sub_len)
{
if (j==-1 || str[i] == sub[j])
{
i++;
j++;
}
else//j回退到next[j]
{
j = next[j];
//极端情况下：i
// a b c ...
// p b c ...
// j
//极端情况下：j刚开时和i就匹配不上，j = next[j];因为next[0]=-1,j=-1
}
}
free(next);
next=NULL;
if (j >= sub_len)
{
return i - j;
}
else
{
return -1;
}
}
int main()
{
int ret = KMP("abdabccd", "abc", 0);
printf("%d\n", ret);
return 0;
}
next数组的优化
i 可以一步回退到位，而不是一直一直回退
练习：