kmp算法:我们所忽略的字符串匹配本质

一、先捅破窗户纸前后缀在匹配里到底起什么作用在讲next数组的计算之前我们必须先把“为什么有前后缀就能不回退主串”这个核心逻辑彻底讲透这是字符串匹配的本质核心。我们用一个有前后缀的经典案例把抽象逻辑落地主串Sabababaca模式串Pababaca我们先看匹配的关键节点我们从S[0]和P[0]开始比对一路匹配到S[4]a 和 P[4]b全部匹配成功此时已匹配的区间是S[0-4] ↔ P[0-4]也就是子串ababa接下来比对S[5]b 和 P[5]c匹配失败这时候暴力匹配会怎么做主串指针直接回退到S[1]模式串指针回退到P[0]从头再来。但你一眼就能发现这里的无效劳动已经匹配成功的ababa里有大量可以复用的信息。我们看ababa这个已匹配的子串它的最长相等前缀是aba最长相等后缀也是aba。这意味着什么意味着主串里已经匹配成功的后缀aba和模式串开头的前缀aba是完全一模一样的既然已经确认了它们相等我们根本不用再重新比对这3个字符只需要让模式串的前缀aba直接对齐主串里已经匹配好的后缀aba然后从模式串前缀的下一位也就是P[3]继续和主串当前的S[5]比对即可。这就是我前面说的“匹配过的字符重新当头”——那些已经匹配成功的后缀字符刚好和模式串的前缀完全一致它们可以直接成为新的匹配起点我们完全不需要让主串指针往回走去重复验证这些已经确定相等的内容。到这里KMP的核心本质已经呼之欲出KMP算法本质是通过预处理模式串为每一个位置提前计算好当这个位置匹配失败时模式串指针可以跳到哪个位置既能最大化复用已经匹配成功的字符又能保证不会错过正确的匹配位置最终实现主串指针全程不回退每个字符只被比对一次。二、next数组给它一个“人话”定义而非教科书式的干巴巴规则我们先约定模式串P的下标从0开始长度为m。next数组是一个和模式串长度相同的数组next[i]的核心含义是当模式串的P[i]位置和主串匹配失败时模式串指针应该回退到next[i]的位置继续和主串当前指针比对无需重新比对前面的字符。而这个next[i]的值刚好等于模式串中P[0]到P[i-1]这个子串的最长相等前后缀的长度。这里一定要注意是P[0]到P[i-1]不是P[0]到P[i]这是90%的人初学都会踩的坑也是硬记公式永远记不住的根源。为什么是i-1因为当P[i]匹配失败时只有P[0]到P[i-1]是已经和主串匹配成功的部分我们要复用的只能是这部分里的相等前后缀。我们用上面的模式串Pababaca手算一遍完整的next数组你会发现它和我们前面的匹配场景完全对应模式串下标i0123456P[i]字符ababacanext[i]-1001230手算逻辑拆解next[0]模式串第0位就匹配失败说明P[0]和主串当前字符完全不匹配我们只能让主串指针后移一位模式串指针还是停在0。所以我们约定next[0] -1这是一个哨兵位专门用来标记“主串指针需要后移”后面你会看到它的妙用。next[1]看P[0]到P[0]的子串a单个字符没有前后缀最长相等前后缀长度为0所以next[1]0。next[2]看P[0]到P[1]的子串ab前缀a和后缀b不相等长度为0next[2]0。next[3]看P[0]到P[2]的子串aba最长相等前缀a和后缀a长度为1next[3]1。next[4]看P[0]到P[3]的子串abab最长相等前缀ab和后缀ab长度为2next[4]2。next[5]看P[0]到P[4]的子串ababa最长相等前缀aba和后缀aba长度为3next[5]3。next[6]看P[0]到P[5]的子串ababac无相等前后缀长度为0next[6]0。你看我们前面匹配失败的位置是P[5]next[5]3刚好就是我们说的“最优起跳点”完美对应。三、next数组的推导本质是模式串自己和自己做KMP匹配很多人觉得next数组的代码晦涩难懂其实是因为没看懂一个核心真相next数组的推导过程本身就是一次KMP匹配——模式串自己既是主串也是模式串我们要做的就是用模式串的后缀去匹配模式串的前缀找到每一个位置的最长匹配长度。它的推导逻辑和后面主串与模式串的匹配逻辑完全一致从头到尾贯彻同一个核心思想主指针永不回退只调整副指针最大化复用已匹配的信息。这里我们用双指针法推导全程不用递归不用复杂公式3条核心规则记一辈子都不会忘定义两个指针前缀指针j初始值为-1指向当前已经匹配成功的前缀的末尾后缀指针i初始值为0指向当前正在遍历的后缀的末尾核心规则规则1当j -1或者P[i] P[j]时i和j都向后移动一位然后令next[i] j含义j-1说明匹配从头开始或当前两个字符相等我们找到了更长的相等前后缀直接记录下来规则2当P[i] ! P[j]时令j next[j]含义当前字符不匹配让j回退到next[j]的位置复用已经匹配的前缀继续比对和KMP匹配逻辑完全一致规则3循环执行直到i遍历完整个模式串。我们还是用Pababaca完整走一遍推导过程你会发现结果和手算完全一致初始状态i0j-1next[0]-1第1轮j-1符合规则1 → i1j0next[1]0第2轮i1j0P[1]b≠P[0]a符合规则2 → jnext[0]-1此时j-1符合规则1 → i2j0next[2]0第3轮i2j0P[2]aP[0]a符合规则1 → i3j1next[3]1第4轮i3j1P[3]bP[1]b符合规则1 → i4j2next[4]2第5轮i4j2P[4]aP[2]a符合规则1 → i5j3next[5]3第6轮i5j3P[5]c≠P[3]b符合规则2 → jnext[3]1仍不匹配jnext[1]0仍不匹配jnext[0]-1此时j-1符合规则1 → i6j0next[6]0这就是KMP最精妙的设计之一它用完全自洽的一套逻辑既完成了next数组的预处理又完成了主串和模式串的匹配没有任何多余的设计算法的美感体现得淋漓尽致。【代码实现】求next数组#include iostream #include vector #include string using namespace std; // 功能计算模式串P的next数组 // 参数P - 模式串 // 返回next数组vectorint类型长度等于P.size() vectorint getNext(const string P) { int m P.size(); vectorint next(m, 0); int j -1; // 前缀指针初始为-1哨兵位 int i 0; // 后缀指针初始为0 next[0] -1; // 初始化next[0]为-1 while (i m - 1) { // 规则1j-1 或 P[i]P[j]双指针后移记录next[i] if (j -1 || P[i] P[j]) { i; j; next[i] j; } // 规则2字符不匹配j回退到next[j] else { j next[j]; } } return next; }四、完整的KMP匹配流程把所有逻辑串起来现在我们有了next数组就可以完整走一遍KMP的匹配流程彻底看懂它是怎么做到O(nm)的线性时间复杂度的。还是用之前的案例主串Sa b a b a b a c a下标0-8长度9模式串Pa b a b a c a下标0-6长度7next数组[-1, 0, 0, 1, 2, 3, 0]匹配的核心规则和next数组的推导逻辑完全一致同样只有3条定义主串指针i0模式串指针j0当j -1或者S[i] P[j]时i和j都向后移动一位当S[i] ! P[j]时令j next[j]终止条件如果j等于模式串的长度m说明匹配成功返回起始位置i-j如果i遍历完主串j还没到m说明匹配失败返回-1我们一步步走完整个匹配过程初始i0j0S[0]a P[0]a → i1j1S[1]b P[1]b → i2j2S[2]a P[2]a → i3j3S[3]b P[3]b → i4j4S[4]a P[4]a → i5j5S[5]b ≠ P[5]c → 匹配失败jnext[5]3此时j3S[5]b P[3]b → i6j4S[6]a P[4]a → i7j5S[7]c P[5]c → i8j6S[8]a P[6]a → i9j7此时j7等于模式串的长度7匹配成功返回起始位置i-j9-72也就是主串中从下标2开始就是模式串的完整位置完全正确。你会发现整个过程中主串指针i从0走到9全程没有往回退过一步主串的每一个字符只被比对了一次这就是KMP比暴力匹配快的核心原因。【代码实现】KMP核心匹配函数// 功能KMP算法主匹配函数 // 参数S - 主串P - 模式串 // 返回模式串在主串中第一次出现的起始下标未找到返回-1 int kmpSearch(const string S, const string P) { int n S.size(); int m P.size(); if (m 0) return 0; // 空模式串默认匹配成功 if (n m) return -1; // 主串比模式串短直接失败 // 1. 预处理获取next数组 vectorint next getNext(P); int i 0; // 主串指针永不回退 int j 0; // 模式串指针 while (i n j m) { // 规则1j-1哨兵位主串后移或字符匹配双指针后移 if (j -1 || S[i] P[j]) { i; j; } // 规则2字符不匹配模式串指针回退到next[j] else { j next[j]; } } // 终止条件判断j走完模式串说明匹配成功 if (j m) { return i - j; // 返回起始下标 } return -1; // 匹配失败 }五、补充被很多人忽略的next数组优化nextval数组最后我们补充一个绝大多数教程会提到但很少讲透本质的优化nextval数组。我们先看一个经典的反例模式串Paaaaab它的next数组是[-1,0,1,2,3,4]。如果主串Saaabaaaaab当匹配到S[3]b和P[3]a时匹配失败jnext[3]2此时S[3]b和P[2]a还是不匹配jnext[2]1还是不匹配jnext[1]0还是不匹配jnext[0]-1。你看这里做了4次完全无效的回退——因为P[3]、P[2]、P[1]、P[0]都是a和P[3]的值完全一样既然P[3]和主串不匹配那前面的a肯定也不匹配这些回退完全是多余的。所以nextval数组的优化本质就是消除这些无效的回退当我们计算next[i]时如果P[i] P[next[i]]那么我们就把next[i]更新为next[next[i]]直接跳过上一个相同的字符避免无效比对。还是用Paaaaab计算它的nextval数组模式串下标i012345P[i]字符aaaaabnext[i]-101234nextval[i]-1-1-1-1-14优化后刚才的匹配失败场景j会直接从3跳到-1一步到位完全消除了无效回退。【代码实现】优化版nextval数组// 功能计算优化后的nextval数组 // 参数P - 模式串 // 返回nextval数组 vectorint getNextval(const string P) { int m P.size(); vectorint nextval(m, 0); int j -1; int i 0; nextval[0] -1; while (i m - 1) { if (j -1 || P[i] P[j]) { i; j; // 【核心优化】如果当前字符和回退位置的字符相同继续回退 if (P[i] P[j]) { nextval[i] nextval[j]; } else { nextval[i] j; } } else { j nextval[j]; } } return nextval; } // 【优化版匹配函数】使用nextval数组 int kmpSearchOptimized(const string S, const string P) { int n S.size(); int m P.size(); if (m 0) return 0; if (n m) return -1; // 使用优化后的nextval数组 vectorint nextval getNextval(P); int i 0; int j 0; while (i n j m) { if (j -1 || S[i] P[j]) { i; j; } else { j nextval[j]; } } if (j m) return i - j; return -1; }【完整可运行示例】把所有代码拼在一起用我们的经典案例测试一下int main() { string S abababaca; // 主串 string P ababaca; // 模式串 // 1. 测试基础版KMP int pos kmpSearch(S, P); cout 【基础版KMP】模式串在主串中的起始下标: pos endl; // 预期输出2 // 2. 测试优化版KMP int posOpt kmpSearchOptimized(S, P); cout 【优化版KMP】模式串在主串中的起始下标: posOpt endl; // 预期输出2 // 3. 打印next数组和nextval数组对照手算结果 vectorint next getNext(P); vectorint nextval getNextval(P); cout \n模式串: P endl; cout next数组: ; for (int val : next) cout val ; cout \nnextval数组: ; for (int val : nextval) cout val ; cout endl; return 0;