★ FEATURED ARTICLE 1. 为什么要学KMP先看看暴力匹配到底浪费在哪1.1 字符串匹配是日常开发里最不起眼的基本功KMP这三个字母是谁的缩写不重要重要的是它解决的那件小事——字符串匹配。别小看这件事编辑器里的查找替换、日志系统里的关键字过滤、爬虫程序里的内容提取、文本处理里的模式定位底层都绕不开它。你输入一段关键词程序要在几万行文本里找出所有出现位置背后跑的就是这一类的算法。从定义上说字符串匹配就是给定一个主串T长度为n再给一个模式串P长度为m我们要找P第一次出现在T里的起始下标。举个最简单的例子T是“hello world”P是“world”匹配结果就是下标6。如果T里根本没有P就返回-1或者一个约定好的值。很多语言本身提供了查找函数比如标准库里的字符串查找、正则表达式引擎等等所以有人会觉得没必要自己实现。但理解KMP的真正价值有几个层面第一它是面试和算法考核里的常客绕不过去第二它把最坏时间复杂度从O(n*m)降到了O(nm)在大文本场景下非常关键第三它的设计思路也就是“利用已经比较过的信息避免重复劳动”影响了后面大量的字符串算法。1.2 暴力匹配是怎么做的在没人教KMP之前大多数人写字符串匹配都会先写“暴力版”。思路非常直白把主串的每一个位置都当作一个可能的起点从那里开始和模式串逐字符比较一旦发现不同就把起点往后移动一位重新比较。写成C语言差不多是这样int bruteSearch(const char *t, const char *p) { int n strlen(t), m strlen(p); for (int i 0; i m n; i) { int j 0; while (j m t[i j] p[j]) { j; } if (j m) { return i; } } return -1; }外层循环决定起点内层循环做逐位比较。这种写法简单、直观、不容易出错但性能隐患非常大。假设主串是“aaaaaaaaaaaaaaaaab”模式串是“aaaab”当起点在0的时候前4个字符都相等到第5个字符才发现不一样于是起点挪到1又重复比较前4个字符……每次都做同样的工作直到最后才找到答案。这个例子的复杂度一眼就能看出来主串长度几乎全是重复字符模式串长度又比较长最坏情况下要做接近n*m次字符比较。很快慢到没法接受。更残酷的是这还不是故意构造的极端数据现实里搜索重复序列、固定内容、模板片段都可能撞上类似情况。1.3 暴力浪费的根源到底在哪暴力法的核心浪费在于失配以后把已经比较过的信息全部丢掉了。主串的指针要回退模式串的指针也要从头再来等于之前读过的那一串字符全都白读。举个例子你在一个非常长的文本里查找一个段落关键词读到了第2000个字符才失配暴力法会把这个位置前后已经确认过的内容全部作废转回去从第2个字符再读一遍。这种重复劳动的频率一高性能就崩了。KMP的思路一反常识主串指针永远不回退失配之后只让模式串指针移动。这听起来像是不可能完成的任务因为它必须知道“模式串应该跳到哪个位置继续”而这个跳转信息就是KMP里的核心——next数组。2. KMP的核心思想前缀后缀与next数组2.1 用生活里的直觉理解“记住已有信息”设想一下你在一本书里找一句之前见过的话读到某一页时发现后面接的内容对不上。你不会翻回第一页重新读你会站在原地思考刚才看到的这段文字里最后几个字和我要找的那句话的开头重复了吗如果重复了那就从这个重复点后面继续往下找。KMP干的正是这件事。它之所以让主串指针不回退是因为在每一轮匹配中主串里已经有一段字符被确认过“和模式串的前若干字符相同”。失配发生时这段已确认的字符并没有作废它的尾部和模式串的头部可能有一部分重叠。只要把模式串向右滑动到让那段重叠的头部对准刚刚扫过的尾部就可以直接从失配字符接着比较完全不用把主串指针退回去。所以KMP要解决的第一个问题就是“模式串自己的前缀和后缀能有多长的重叠”。这个重叠长度就是跳过无效比较的依据。2.2 真前缀与真后缀的定义为了避免术语劝退先把两个概念用最简单的话说清楚。一个字符串的前缀就是从左往右截出来的若干个连续字符后缀就是从右往左截出来的若干个连续字符。注意这里说的都是“真前缀”和“真后缀”也就是不能取整个字符串自己。比如“ABABC”它的真前缀有“A”、“AB”、“ABA”、“ABAB”它的真后缀有“C”、“BC”、“ABC”、“BABC”。两边都不包含“ABABC”本身。如果某个前缀和后缀一模一样那就叫“公共前后缀”。把长度最长的那一个找出来长度值就是“最长公共前后缀长度”。例如“ABAB”这个字符串真前缀里有一个“AB”真后缀里也有一个“AB”所以最长公共前后缀长度是2。而“ABABC”里没有长度超过0的公共前后缀所以这个值是0。理解到这一步KMP就已经入门了一半。next数组本质上就是在回答一个简单的问题模式串从左到右逐位增长时每一截的最长公共前后缀分别是多少。2.3 next数组到底存了什么东西网上关于next数组的代码五花八门主要原因是对next数组的定义不统一。我在这篇文章里先采用一种最常见的定义next[j]表示模式串P从开头到下标j-1这一段的“最长公共前后缀长度”并且约定next[0] -1。为什么要有-1这种奇怪的值因为next数组不止要存“长度信息”还要在匹配时作为“失配跳转的下标”来用。当模式串第0个字符就失配时它已经没有任何前缀可以对齐了这时候必须让主串指针前进一位模式串还是从0开始。用-1作为一个特殊标记恰好方便代码里统一判断。举个例子模式串是“ABAB”那么next[0] -1约定值next[1]考察的是“A”最长公共前后缀长度为0next[2]考察的是“AB”最长公共前后缀长度为0next[3]考察的是“ABA”前缀“A”和后缀“A”相同长度为1失配跳转时如果当前比较到了P[j]但字符不相等就让j next[j]然后用新的P[j]继续和主串当前位置比较。也就是说next数组是一张“失配之后下一步怎么办”的跳转表它把匹配失败时浪费的比较全部省掉了。3. 手把手计算next数组两个实例讲透3.1 用模式串“ABABCABAB”完整推导空口讲定义不够直观我们直接拿一个模式串手工推导一遍。给定P “ABABCABAB”长度是9下标从0到8。逐步计算j被考察的子串P[0..j-1]最长公共前后缀next[j]0空无-11A无02AB无03ABAA长度114ABABAB长度225ABABC无06ABABCAA长度117ABABCABAB长度228ABABCABAABA长度33自己动手算的时候我推荐一个笨办法把每一段的真前缀和真后缀先列出来再找相同项。比如“ABABCABA”前缀集合包括A、AB、ABA、ABAB、ABABC、ABABCA、ABABCAB后缀集合包括A、BA、ABA、CABA、BCABA、ABCABA、BABCABA。两边都出现的最长项是“ABA”长度3所以next[8]等于3。这个值在实际匹配中是什么意思当模式串比较到第8个字符失败时说明它之前匹配成功了8个字符也就是“ABABCABA”。这时候模式串已经读过的内容里尾部3个字符“ABA”和头部3个字符“ABA”完全一致所以可以让模式串直接跳到下标3拿P[3]和刚才失配的主串字符重新比较。这样就不会把“ABA”这3个字符再重新匹配一遍。3.2 为什么网上有两种稍微不同的next定义很多初学者最大的困惑就是同一个模式串在这个教程里next是这么写的在那个教程里next是那样写的看代码好像都对混着用却错得离谱。两种常见的定义分别是第一种前缀函数式定义next[j]表示P[0..j-1]的最长公共前后缀长度next[0] -1。这也是一部分教材的做法。第二种失配跳转式定义next[j]表示匹配到P[j]失配时模式串下一步应该跳到的下标。这种定义通常会把上一个定义的next数组整体右移一位再在最前面补一个-1或者从0开始编号时做其它调整。网上有些教程还会把这两种定义混着写所以你会看到有的地方next[3]1有的地方next[3]0看得一头雾水。其实算法本身没有变化变的只是表的“存储格式”。我个人建议你先固定住上面第一种定义因为它和“最长公共前后缀”这个概念直接对应手算的时候不容易出错。等你把第一种定义下的算法彻底搞懂了再去看第二种写法会发现只是把下标错位了一下并不难理解。千万别同时背好几套模板否则写代码的时候一定会乱。4. 代码实现从next到完整的KMP匹配4.1 求next数组巧用“模式串匹配自己”KMP代码里最容易被卡住的地方就是next数组的生成过程。其实它的原理可以概括成一句话拿模式串自己和自己做匹配。通俗地说我们让两个指针分别跑在模式串的“前缀”和“后缀”上。一个指针记录当前已经匹配到多长的前缀另一个指针遍历模式串的每一个位置一旦发现后缀里出现了前缀的影子就记录下这个重叠长度。void getNext(const char *p, int *next) { int m strlen(p); next[0] -1; int i 0, j -1; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } }这里i可以理解成“后缀部分的末尾”j可以理解成“前缀部分的末尾”。初始时j -1表示前缀还没有任何字符匹配上。循环里只有两种情况当前的p[i]和p[j]相等说明公共前后缀可以继续延长于是i和j一起前进并且记录下next[i] j。两者不相等说明这个位置不能继续延长了j要按已经算好的next数组回退相当于“用模式串自己的失配信息来指导下一步”。为什么循环条件是i m - 1因为next[m-1]指的是P[0..m-2]的公共前后缀长度它会在i m-2那一步被记录而next[m]在匹配过程中用不到模式串整体匹配成功就结束了不需要为“第m个字符失配”准备跳转信息。4.2 匹配主循环失配时怎么跳有了next数组KMP的主匹配函数就非常简单了。主串指针i始终向前走模式串指针j按照next数组来回调整。int kmpSearch(const char *t, const char *p) { int n strlen(t), m strlen(p); if (m 0) { return 0; } int *next (int *)malloc(sizeof(int) * m); getNext(p, next); int i 0, j 0; while (i n j m) { if (j -1 || t[i] p[j]) { i; j; } else { j next[j]; } } free(next); if (j m) { return i - j; } return -1; }写这段代码的时候有两点要特别注意。第一当j变成-1时说明模式串的前缀彻底对不上了主串指针必须前进一位模式串从头开始比较。所以代码里判断了“j -1”这个条件它和“字符相等”被放在同一个分支处理是因为这两种情况都会让i和j同时往前推进。第二匹配成功后返回的是i - j因为循环结束时i已经指向主串中匹配段末尾的下一个位置减去模式串长度j就是这段匹配的起始下标。严格来说上面这种写法还没做“连续重复字符”的优化但这不影响正确性也不影响理解。我建议初学者先把这一步跑通再说优化。4.3 nextval优化解决连续重复字符的重复劳动如果一次失配后新的P[j]和刚刚失配的P[j_old]完全相同那么跳到新位置后还是会失配等于白跳了一次。针对这个问题可以在生成next时做一层判断如果当前要填入的next[i]和模式串对应位置的字符相同就继续往前回溯。优化后的生成函数长这样void getNextVal(const char *p, int *next) { int m strlen(p); next[0] -1; int i 0, j -1; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; if (p[i] p[j]) { next[i] next[j]; } else { next[i] j; } } else { j next[j]; } } }对比一下能发现逻辑主体没变只在给next[i]赋值前加了一个判断。这个优化在模式串有大量重复字符时收益很明显比如模式串是“AAAAA”遇到失配时原本可能需要连续跳好几步优化后一步就定位到正确位置。网上很多代码把这个版本直接叫next数组实际上它更准确的名字是nextval。奉劝新手不要纠结两个名字先能把基础版写对优化版不过是多了个“防止重复比较”的小技巧而已。5. 完整匹配流程走读每一步都有据可查5.1 真实例子主串“abcabxabcabd”与模式串“abcabd”光看代码还是不直观我们完整走一遍匹配过程。主串T “abcabxabcabd”模式串P “abcabd”。先算P的next数组。P “abcabd”长度6next[0] -1考察“a”next[1] 0考察“ab”next[2] 0考察“abc”next[3] 0考察“abca”最长公共前后缀是“a”next[4] 1考察“abcab”最长公共前后缀是“ab”next[5] 2所以next {-1, 0, 0, 0, 1, 2}。接下来从i0、j0开始匹配。步骤ij比较内容结果下一步000T[0]aP[0]a匹配i1j1111T[1]bP[1]b匹配i2j2222T[2]cP[2]c匹配i3j3333T[3]aP[3]a匹配i4j4444T[4]bP[4]b匹配i5j5555T[5]xP[5]d失配jnext[5]2652T[5]xP[2]c失配jnext[2]0750T[5]xP[0]a失配jnext[0]-185-1特殊分支处理i6j0960T[6]aP[0]a匹配i7j11071T[7]bP[1]b匹配i8j21182T[8]cP[2]c匹配i9j31293T[9]aP[3]a匹配i10j413104T[10]bP[4]b匹配i11j514115T[11]dP[5]d匹配i12j6最终j6等于模式串长度m返回i-j12-66也就是主串下标6。整个过程里主串指针i从0增加到12从来没有回退过。模式串指针j虽然经历了一次次回跳但它的回跳完全靠next数组完成不会触发主串重新扫描。这就是KMP带感的地方。5.2 失配跳转为什么不漏掉可能的匹配看到这里不少人的第一反应是主串指针一直往前走万一真正的匹配起点被跳过去了怎么办答案藏在next数组的性质里。假设我们在i位置失配说明主串从某个位置到i-1这段刚好和模式串的P[0..j-1]完全相等。也就是说主串当前位置前面这一段的后缀等于模式串这一截的前缀。把模式串向右滑动让这个相同的前后缀对准那么模式串开头的那部分字符已经天然和主串匹配好了完全不需要再比较。真正被跳过的是那些已经被证明不可能成为匹配起点的位置。因为模式串要匹配成功它开头的字符必须和主串某一段完全一致而主串刚刚从前往后扫过的每段情况都已经记录在案凡是不可能的地方模式串要么滑过去要么被next数组直接规避。这个“不回溯且不遗漏”的特点正是KMP区别于暴力法的根本原因。6. 复杂度分析KMP快在哪里慢在何处6.1 两个循环的均摊分析KMP的时间复杂度为什么是O(nm)要解释清楚得分别看它的两个阶段。先看主匹配循环。主串指针i在每次比较后要么前进要么保持不变但i只有在“字符匹配成功”或“j为-1”时才会增加。所以整个匹配过程中i最多增加n次这一点没有争议。那j不断回跳会不会导致循环次数爆炸不会。j的每一次回跳都是因为之前j曾经从某个较小值增加到了当前值。也就是说j能回跳多少次取决于j之前一共增加过多少次。j增加一次往往伴随着i增加一次所以j回跳的总次数被n限制住。综合下来主循环的总执行次数是O(n)。再看生成next数组的过程。它本质上就是模式串自己和自己匹配模式和主循环一模一样只是“主串”变成了模式串自身。所以它的总执行次数是O(m)。合在一起KMP的时间复杂度是O(nm)。这个结论在数学上成立在实际运行中也站得住脚。空间上多了一个长度为m的next数组所以空间复杂度是O(m)。6.2 “线性”背后的几个真相线性复杂度听起来很美好但有几个细节需要泼一下冷水。第一KMP的常数项不算小。每次失配都要读取next数组再根据结果调整指针过程中还多了一次额外判断。如果主串很短、模式串很短KMP未必比暴力法快多少。它真正的优势体现在大规模文本、重复模式或者最坏情况频发的场景里。第二随机文本下暴力法往往表现不差。因为大多数情况下模式串的第一个字符就能让大多数起点立刻失败暴力法很多时候实际复杂度接近O(n)。所以不存在“任何时候KMP都碾压暴力”的说法。第三KMP的空间占用虽然只有O(m)但在现代缓存友好的算法面前单次字符访问的顺序性和局部性也可能影响到实际性能。这就是为什么很多成熟的文本工具会选用其它更激进的匹配策略而不是一律套KMP。7. 避坑清单与验证方法7.1 先统一next定义再写代码我见过太多人写代码前不定义清楚next数组的含义直接照抄网上的模板结果抄出来的代码在某些用例上正确换一个模式串就崩。比如有的模板里next[0]-1有的模板里next[0]0有的模板里next[i]记录的是“长度”有的模板里记录的是“跳转位置”。一旦你把两种模板拼在一起逻辑立刻错乱。我的建议是写之前先在注释里写清楚“next[j] P[0..j-1]的最长公共前后缀长度next[0]-1”。然后严格按照这个定义去验证几个模式串跑通了再继续。7.2 几个必须测试的边界用例字符串算法的边界问题特别多凡是靠肉眼检查代码很难发现。我一般会用下面这组用例做快速验证模式串为空串应该返回0而不是越界访问主串为空串应该返回-1模式串长度大于主串直接返回-1模式串和主串完全相同返回0模式串只有一个字符检查匹配逻辑是否依赖ne数组越界模式串全是重复字符比如“aaaaab”和主串“aaaaaaaaaaab”模式串存在大量重叠后缀比如“ababa”和主串“xxababaxx”这组用例覆盖了大部分容易出错的场景跑通了基本没有大问题。7.3 用对拍方法验证正确性如果你觉得手推太累最可靠的方式是对拍。也就是写一个暴力匹配函数再写一个KMP函数然后生成大量随机字符串对比两者返回的起始下标是否完全一致。哪怕只生成几百组长度为几十的随机串也能把大多数隐性问题暴露出来。我自己经常用Python写个几十行的小脚本做这件事。核心逻辑就是for循环里随机生成主串和模式串分别调用两个实现发现结果不一致就打印出来。需要注意的是生成随机串时不要只用普通字母还应该加入少量重复字符集合比如只从“aaaaaa”和“bbbbbb”这种字符池里取这样才能覆盖KMP最容易出错的连续重复场景。7.4 一个容易忽略的细节模式串重复字符的nextval有的同学测试普通模式串时一切正常一到“ABABABA”这类高重复模式串就出问题原因往往是把未优化的next和优化版的nextval混用了。未优化版本的next值在某些连续重复字符场景下会让j跳好几次。优化版本的nextval直接跳到了更远的位置。两者虽然在最终结果上一致但产生的跳转序列不同如果调试时看跳转过程会觉得逻辑对不上。我的经验是学习阶段只用未优化版本理解清楚以后再换优化版不要一上来就背着nextval的模板糊里糊涂地抄。8. 我的学习路线参考如果让我重新学一遍KMP我会按下面这个顺序走。第一步先用暴力法写一个能跑通的字符串匹配再构造一个类似“aaaaaaaaab”和“aaaab”的用例亲眼看看暴力法到底慢在哪。第二步花一整个下午手推三个模式串的next数组每个位置都画出前缀后缀集合不跳步。第三步自己实现主匹配代码并对着第5小节的完整例子走一遍流程。第四步再去看nextval优化这时候你会发现所谓的优化不过是一层小判断。最后再分享一个实操技巧实在记不住代码时不用硬背模板只要记住两个原则就够了——next记录的是“已经匹配过的部分里前缀后缀最长的重叠长度”主循环里失配后让j next[j]而不是让i回退。这两句话想通了代码是能现场写出来的。KMP不是那种一遍就能彻底吃透的算法我当年也推错过好几次next数组。但正因为它的设计绕了几个弯真正理解之后你会发现字符串匹配背后“用历史信息指导未来跳转”的思路在算法世界里到处都是它的影子。
阅读完成 · 觉得有帮助？
