KMP算法：高效字符串匹配秘诀

一、先解答上次的思考题问BF 算法为什么慢答每次匹配失败主串 i 要回退、模式串 j 要归零大量重复比较浪费时间。二、今天学习目标理解 KMP 核心不回退主串 i理解next 数组最长相等前后缀手写 next 数组KMP 完整代码 实战匹配三、KMP 是什么KMP 三位作者首字母解决BF 重复回溯、效率低的问题核心思想主串 i 永远不回退模式串 j 利用前后缀信息跳到合适位置继续匹配时间复杂度O(n m)四、关键最长相等前后缀next 数组例子模式串ababc前缀a, ab, aba, abab后缀c, bc, abc, babc最长相等前后缀长度2abnext[j]当模式串第 j 位失配时j 应该跳回的位置。五、next 数组代码最关键void getNext(char pat[], int next[]) { int len strlen(pat); next[0] -1; int j 0; int k -1; while (j len - 1) { if (k -1 || pat[j] pat[k]) { j; k; next[j] k; } else { k next[k]; } } }六、KMP 匹配完整代码#include stdio.h #include string.h void getNext(char pat[], int next[]) { int len strlen(pat); next[0] -1; int j 0; int k -1; while (j len - 1) { if (k -1 || pat[j] pat[k]) { j; k; next[j] k; } else { k next[k]; } } } int KMP(char str[], char pat[]) { int len_str strlen(str); int len_pat strlen(pat); int next[len_pat]; getNext(pat, next); int i 0; int j 0; while (i len_str j len_pat) { if (j -1 || str[i] pat[j]) { i; j; } else { // 只回退 ji 不动 j next[j]; } } if (j len_pat) { return i - j; } return -1; } // 测试 int main() { char str[] ababcabcac; char pat[] abcac; int pos KMP(str, pat); if (pos ! -1) { printf(匹配成功位置%d\n, pos); } else { printf(匹配失败\n); } return 0; }运行结果匹配成功位置5七、KMP 核心一句话记住BFi 回退j 归零KMPi 不回退j 跳 next八、今日小练习主串abababcabc模式串abc用 KMP 代码求匹配位置。