KMP算法详解 [c++]

目录前言朴素的模式匹配算法KMP模式匹配算法KMP模式匹配算法的原理next数组值的推导KMP模式匹配算法的实现KMP模式匹配算法的改进nextval的推导优化后的KMP模式匹配算法代码零、前言每年新闻周刊都会发布年度十大热词这其实查询某个字符串在其他字符串中的出现频率我们专业学习中经常阅读专业文献晦涩的专业词汇经常惹人头疼如果我们能编写一个程序实现输入一段文本就能够查询到其中频率最高的一些词汇然后专攻这些词汇无疑会大大提升我们的工作效率这种在一篇文章中去找一个单词的定位问题其实就是子串的定位操作通常称做串的模式匹配。一、KMP算法1.1朴素模式匹配在语言学习阶段经常遇到查找一个子串在母串中的位置要求返回字串第一个字符在母串中的下标。对于当时还是小白的我们自然会选择暴力求解的朴素解法。从母串的第一个字符开始匹配匹配成功就比对母串和子串的下一个匹配失败就从母串第二个字符继续下去以此类推。这样的时间效率显然是很差的假如母串长度为N 子串长度为M 最差的时间复杂度为O(M * N)int strstr(const string dst, const string src) //返回src在dst中出现位置的首字符下标 { if (dst.size() src.size()) return -1; int i 0, j 0; while (i (int)dst.size() j (int)src.size()) { if (dst[i] src[j]) { i; j; } else { i i - j 1; j 0; } } if (j src.size()) return i - j; else return -1; }上面的写法对于我们初学C语言时掌握语法理解指针是很有帮助的但是随着水平的提高我们自然不能容忍效率这样低下的算法1.2 KMP模式匹配算法有三位前辈,D.E.Knuth、J.H.Morris和V.R.Pratt其中Knuth 和Pratt共同研究,Morris独立研究发表—个模式匹配算法,可以大大避免重复遍历的情况,我们把它称之为克努特-莫里斯-普拉特算法简称KMP算法。1.3 KMP模式匹配算法的原理对于朴素算法而言如果主串S“abcdefgab”,其实还可以更长-些,我们就省略掉只保留前9位,我们要匹配的T“abcdex”’那么如果用前面的朴素算法的话’前5个字母’两个串完全相等,直到第6个字母’“f”与‘‘x”不等’如下图所示。按照接下来的流程我们对母串接连重复第一次的匹配操作我们发现后面五次操作都是冗余的因为我们知道子串中a和后面的字符均不相等所以对于母串中的“bcde“就没有必要进行匹配了。那么如果我们子串中a后面也有a出现呢我们看下面的母串”abcababca“和子串”abcabx“我们发现对于23操作是多余的而4操作是有意义的(虽然也没有匹配成功但是起码有重合的部分)看到这里即使还没有介绍KMP模式匹配算法的原理你也应该能猜出来了KMP算法其实就是省略了朴素算法中的冗余操作如果用i j分别来表示母串和子串中的枚举下标那么KMP就保证了下标i永不回溯换句话说就是i一直往后移动在失败的时候令j回溯从而保证了时间效率。而j的回溯规则取决于子串中结构是否有重复的问题。再比如下图由于子串”abcdex“没有重复的部分所以j由6回溯到了1但是上图中由于”abcabx“中有重复部分”ab“所以j就由6回溯到了3因此,我们可以得出规律j的大小取决于当前字符之前的串的前后缀的相似度。这也就有了一个前提我们在查找字符串之前先要对要查询的字符串进行一个分析来提高查找的速度。我们把子串各个位j值的变化定义为一个数组next,那么next的长度就是子串的长度。于是我们可以得到下面的函数定义:回溯位置其实就是j之前最长公共前后缀长度有些地方的KMP算法把j 0的情况回溯到0其实大同小异这里设置成-1再后面代码实现的时候其实会很方便1.4 next数组值的推导通过上面的介绍如果next数组已经给出相信大多数人都是可以自己写出KMP算法的代码的因为它的思路很好理解而难点就在于next数组的推导这其实是子串的子匹配问题掺杂了动态规划的思想。我们先给出一些例子我们发现next[j]的值恰好就是j之前最长公共前后缀长度了解了原理代码实现就不是问题了1.5 KMP模式匹配算法的实现void get_next(const string src, vectorint next) { int j 0, k -1; next[0] -1; while (j (int)src.size() - 1) { if (k -1 || src[j] src[k]) //src[j] 表示后缀的单个字符 //src[k] 表示前缀的单个字符 { j; k; next[j] k; } else { k next[k]; } } } //返回src在dst中从pos开始往后的位置下标不存在就返回-1 int index_KMP(const string dst, const string src, int pos 0) { int i pos, j 0; vectorint next(src.size()); get_next(src, next); while (i (int)dst.size() j (int)src.size()) { if (j -1 || dst[i] src[j]) { i; j; } else { j next[j]; } } if (j (int)src.size()) return i - j; else return -1; }1.6 KMP模式匹配算法的改进后来有人发现KMP其实还是有缺陷的比如对于母串“aaaabcde”子串“aaaaax”其next数组的值为-101234当我们的i , j的值为4的时候j开始回溯回溯到3发现不行再回溯到2再到1最终到-1从而i变为5我们发现对于步骤2345其实都是多余操作这说明我们的next数组其实是有改进的地方的下面我们看一下改进后的nextval数组代码void get_nextval(const string src, vectorint nextval) { int j 0, k -1; nextval[0] -1; while (j (int)src.size() - 1) { if (k -1 || src[j] src[k]) //src[j] 表示后缀的单个字符 //src[k] 表示前缀的单个字符 { j; k; if (src[j] ! src[k]) nextval[j] k; else //如果相等回溯后字符不变所以nextval值是回溯后字符的nextval值 nextval[j] nextval[k]; } else { k nextval[k]; } } }我们新的KMP算法代码只要更改get_next()为get_nextval()即可。1.7 nextval的推导通过上图我们发现nextval相对于next的优化方法其实就是判断回溯字符与当前字符是否相等如果相等说明我们回溯是无效的便将当前位置nextval的值设置为回溯位置的nextval的值这其实就有点动态规划的思想了。1.8 优化后的KMP模式匹配算法代码最后放一下我们的终极代码void get_nextval(const string src, vectorint nextval) { int j 0, k -1; nextval[0] -1; while (j (int)src.size() - 1) { if (k -1 || src[j] src[k]) //src[j] 表示后缀的单个字符 //src[k] 表示前缀的单个字符 { j; k; if (src[j] ! src[k]) nextval[j] k; else //如果相等回溯后字符不变所以nextval值是回溯后字符的nextval值 nextval[j] nextval[k]; } else { k nextval[k]; } } } //返回src在dst中从pos开始往后的位置下标不存在就返回-1 int index_KMP(const string dst, const string src, int pos 0) { int i pos, j 0; vectorint next(src.size()); get_nextval(src, next); while (i (int)dst.size() j (int)src.size()) { if (j -1 || dst[i] src[j]) { i; j; } else { j next[j]; } } if (j (int)src.size()) return i - j; else return -1; }1.9 KMP的复杂度分析updated on 2026.3.16这篇博客是我大二上数据结构课程期间所写十分稚嫩。今天突然想到KMP的板子写了无数次好像没有认真思考过复杂度。无论是建立next数组还是利用next数组来查找目标字符串好像所有人的解释都是 i 指针单调不减j 指针跳前缀所以复杂度是线性的。事实上更严谨的分析方法i 指针单调不降每次i 会带来 j那么 j 跳next 的次数也不会超过 j 增加的次数而 j 增加的次数又取决于 i 增加的次数而i 最多增加n次所以 j 也最多跳 next 跳n次因而next数组和 模式串查找的复杂度都是线性的