前言：一般的书籍或文章教学KMP算法都是从问题分析、思路教学再到代码教学。但是我以为先看懂代码、再捋清思路反而会更容易，所以本文会以代码+代码分析的方式来教学KMP算法。
一、BF算法的代码
- #include #include #include int BF(const char* txt, const char* pat){ int i = 0; int j = 0; int txt_len = strlen(txt); int pat_len = strlen(pat); while (i < txt_len && j < pat_len) { if (txt[i] == pat[j]) { i++; j++; } else { i = i - j + 1; j = 0; } } if (j == pat_len) { return i - j + 1; } return -1;}int main(){ char txt_str[101]; char pat_str[11]; puts("Please input main string (Max 100 chars):"); gets(txt_str); puts("Please input pattern string (Max 10 chars):"); gets(pat_str); printf("Matched position: %d\n", BF(txt_str, pat_str)); return 0;}
当主串的第4个字符和模式串的第4个字符不匹配时：
- 主串：aaaaaaac，模式串：aaab
BF算法：从主串的第2个字符和模式串的第1个字符开始向后匹配；
KMP算法：从主串的第4个字符和模式串的第3个字符开始向后匹配。
- 主串：aaacaaab，模式串：aaab
BF算法：从主串的第2个字符和模式串的第1个字符开始向后匹配；
KMP算法：从主串的第4个字符和模式串的第3个字符开始向后匹配。
可以看到BF算法在字符不匹配时，下一次比对字符的位置会做没有意义的回退。
三、KMP算法的代码
- #include #include #include void init_next(const char* pat, const int pat_len, int* next){ next[0] = -1; int j = 0; int k = -1; while (j < pat_len - 1) { if (k == -1 || pat[j] == pat[k]) { j++; k++; next[j] = k; } else { k = next[k]; } }}int KMP(const char* txt, const char* pat){ int i = 0; int j = 0; int txt_len = strlen(txt); int pat_len = strlen(pat); int* next = (int*)malloc(pat_len); init_next(pat, pat_len, next); while (i < txt_len && j < pat_len) { if (j == -1 || txt[i] == pat[j]) { i++; j++; } else { j = next[j]; } } free(next); next = NULL; if (j == pat_len) { return i - j + 1; } return -1;}int main(){ char txt_str[101]; char pat_str[11]; puts("Please input main string (Max 100 chars):"); gets(txt_str); puts("Please input pattern string (Max 10 chars):"); gets(pat_str); printf("Matched position: %d\n", KMP(txt_str, pat_str)); return 0;}
- 设主串的长度为n，模式串的长度为m，则BF算法的时间复杂度是O(n*m)，空间复杂度是O(1)，KMP算法的时间复杂度O(m+n)，空间复杂度O(m)。
- KMP算法分为两步，第一步是构造next数组（由init_next函数实现，时间复杂度为O(m)，空间复杂度为O(m)），第二步是顺序逐个字符遍历主串（由KMP函数中的while语句实现，时间复杂度为O(n)）。
- 模式串为aaab时，next数组为{-1, 0, 1, 2}。
- 变量i指示主串当前比对的索引位置，变量j指示模式串当前比对的索引位置，变量k指示模式串下一次比对的索引位置。
- next数组的值只与模式串有关，与主串无关，一共pat_len个元素，元素next[j]的值存储的是pat[j]与txt不匹配时下一次与txt比对的pat[k]的模式串索引位置k，k一定比j小。数组中-1和0代表重新从pat[0]开始比对，1代表重新从pat[1]开始比对，2代表重新从pat[2]开始比对，依此类推。
- next[0]一定便是-1，next[1]一定便是0，next[j]的值只与pat[0]到pat[j-1]这j个字符有关，next[j]的值与pat[j]是什么字符无关。
- 现在来讲讲next数组的值要怎么确定。字符串的前缀指除最后一个字符以外，字符串的所有头部子串。字符串的后缀指除第一个字符以外，字符串的所有尾部子串。以模式串aaab为例，next[0]和next[1]是固定值，next[2]的值由pat[0]到pat[1]这个字符串"aa"决定，"aa"的前缀为{a}，后缀为{a}， { a } ∩ { a } = { a } \{a\}\cap\{a\}=\{a\} {a}∩{a}={a}，{a}中最长的子串的长度为1，故next[2]便是1，next[3]的值由pat[0]到pat[2]这个字符串"aaa"决定，"aaa"的前缀为{a,aa}，后缀为{a,aa}， { a , a a } ∩ { a , a a } = { a , a a } \{a,aa\}\cap\{a,aa\}=\{a,aa\} {a,aa}∩{a,aa}={a,aa}，{a,aa}中最长的子串的长度为2，故next[2]便是2。
- 从代码实现的角度来说，在init_next函数中变量k存储的是当前子串（pat[0]到pat[j-1]这j个字符）的最长相等前后缀的前缀最后一个字符的索引位置，各人可以加一些打印自己跑一下代码。
- KMP函数中while循环里做的事情就很简朴了。如果当前字符相同，则继续比对下一个字符，如果当前字符差别，则将主串中的当前字符继续与next数组指定的模式串中的字符比对。如果j到达模式串的末端则退出循环（说明已经匹配到了效果），如果i到达主串的末端了j依然没有到达模式串的末端则说明主串中不存在模式串。
五、KMP算法的进一步优化
- 我们再来思考一种情况，当模式串为abab时：
原来的KMP算法的next数组：{-1, 0, 0, 1}
改进后的KMP算法的next数组：{-1, 0, -1, 0}
- 当txt和模式串的第4个字符’b’不匹配时，老算法会回到模式串的第2个字符’b’开始比对（注意上面两个next数组的第4个元素的差别），改进后的算法会回到模式串的第1个字符’a’开始比对，因为txt既然不便是模式串的第4个字符’b’，那么txt也不会便是模式串的第2个字符’b’。
- 改进前后next数组的差别都与上面这种原因雷同，许多资料也将改进后的next数组称为nextval数组。
- 将init_next函数里if语句中的next[j] = k;语句替换为如下代码即可：
- if (pat[j] != pat[k]){ next[j] = k;}else{ next[j] = next[k];}
来源：https://blog.csdn.net/CharmingSun/article/details/112080172
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ |
