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

云卦逾 · 昨天 16:00

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

众所周知，kmp算法是一个精妙且广为人知的算法，但我们似乎仅仅只是硬记或只是知晓它通过next数组与前后缀去完成匹配，根本没有看到它所精妙的地方。
不久前，我在刷视频时偶然看见了介绍kmp算法的视频，就开始推演我很久之前所学的kmp算法，推演着推演着我发现了我之前所未发现的字符串的匹配本质，以下我开始讲解。
字符串匹配，有一个资源串与目标串，我们先统一术语避免歧义：我们把「资源串」称为主串S（长度为n），「目标串」称为模式串P（长度为m），匹配的核心目标，是找到P在S中第一次出现的起始下标，不存在则返回-1。
我们先假设一个极端理想的条件：模式串没有任何相等的前后缀。在该情况我们可以清晰地发现，主串上的匹配指针完全可以做到不回退。举个例子：主串是abdabcabc，模式串是abc，当模式串指针走到c、和主串的d匹配失败后，主串指针完全不用回退到第二个字符b，直接停在d的位置，让模式串指针回到首字符a继续比对即可——因为我们一眼就能确定，已经匹配过的ab里，没有任何一个字符能和模式串的首字符a匹配，回退纯属无效劳动。
但为什么我们会从O(n²)的暴力匹配算法，一步步迭代出KMP算法？核心原因很简单：现实中的模式串大概率会存在相等的前后缀。当模式串有前后缀时，已经匹配成功的字符，完全可以成为新的匹配起点，我们无需让主串指针回退去重复比对这些已经确认相等的内容。而KMP做的，就是用空间换时间，通过预处理模式串，把所有子串的可复用前后缀信息提前存下来，这个存储信息的数组，就是我们常说的next数组。最终实现：无论模式串是否有前后缀，主串匹配指针全程永不回退。
接下来，我把如何找出目标串子串的前后缀、以及next数组的核心逻辑完整讲透——而这一步，恰恰是大多数人只记公式、却没读懂的KMP的核心灵魂：next数组的本质，从来不是“求最长相等前后缀”，而是为模式串的每一个位置，提前找好“匹配失败时，不用重头再来的最优起跳点”。最长相等前后缀，只是我们计算这个起跳点的数学手段，而非最终目的，很多人学KMP学反了，把手段当成了目的，自然只能硬记公式，看不懂它的精妙。
一、先捅破窗户纸：前后缀在匹配里到底起什么作用？

在讲next数组的计算之前，我们必须先把“为什么有前后缀，就能不回退主串”这个核心逻辑彻底讲透，这是字符串匹配的本质核心。
我们用一个有前后缀的经典案例，把抽象逻辑落地：

主串S：abababaca
模式串P：ababaca

我们先看匹配的关键节点：
我们从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的核心含义是：当模式串的P位置和主串匹配失败时，模式串指针应该回退到next的位置，继续和主串当前指针比对，无需重新比对前面的字符。
而这个next的值，刚好等于模式串中，P[0]到P[i-1]这个子串的最长相等前后缀的长度。
这里一定要注意：是P[0]到P[i-1]，不是P[0]到P！这是90%的人初学都会踩的坑，也是硬记公式永远记不住的根源。
为什么是i-1？
因为当P匹配失败时，只有P[0]到P[i-1]是已经和主串匹配成功的部分，我们要复用的，只能是这部分里的相等前后缀。
我们用上面的模式串P=ababaca，手算一遍完整的next数组，你会发现它和我们前面的匹配场景完全对应：
模式串下标i0123456P字符ababacanext-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不相等，长度为0，next[2]=0。

next[3]：看P[0]到P[2]的子串aba，最长相等前缀a和后缀a，长度为1，next[3]=1。

next[4]：看P[0]到P[3]的子串abab，最长相等前缀ab和后缀ab，长度为2，next[4]=2。

next[5]：看P[0]到P[4]的子串ababa，最长相等前缀aba和后缀aba，长度为3，next[5]=3。

next[6]：看P[0]到P[5]的子串ababac，无相等前后缀，长度为0，next[6]=0。

你看，我们前面匹配失败的位置是P[5]，next[5]=3，刚好就是我们说的“最优起跳点”，完美对应。
三、next数组的推导：本质是模式串自己和自己做KMP匹配

很多人觉得next数组的代码晦涩难懂，其实是因为没看懂一个核心真相：next数组的推导过程，本身就是一次KMP匹配——模式串自己既是主串，也是模式串，我们要做的，就是用模式串的后缀，去匹配模式串的前缀，找到每一个位置的最长匹配长度。
它的推导逻辑，和后面主串与模式串的匹配逻辑完全一致，从头到尾贯彻同一个核心思想：主指针永不回退，只调整副指针，最大化复用已匹配的信息。
这里我们用双指针法推导，全程不用递归，不用复杂公式，3条核心规则记一辈子都不会忘：

定义两个指针：

前缀指针j：初始值为-1，指向当前已经匹配成功的前缀的末尾

后缀指针i：初始值为0，指向当前正在遍历的后缀的末尾

核心规则：

规则1：当j == -1，或者P == P[j]时：i和j都向后移动一位，然后令next = j
（含义：j=-1说明匹配从头开始，或当前两个字符相等，我们找到了更长的相等前后缀，直接记录下来）

规则2：当P != P[j]时：令j = next[j]
（含义：当前字符不匹配，让j回退到next[j]的位置，复用已经匹配的前缀继续比对，和KMP匹配逻辑完全一致）

规则3：循环执行，直到i遍历完整个模式串。

我们还是用P=ababaca，完整走一遍推导过程，你会发现结果和手算完全一致：

初始状态：i=0，j=-1，next[0]=-1

第1轮：j=-1，符合规则1 → i=1，j=0，next[1]=0

第2轮：i=1，j=0，P[1]=b≠P[0]=a，符合规则2 → j=next[0]=-1；此时j=-1，符合规则1 → i=2，j=0，next[2]=0

第3轮：i=2，j=0，P[2]=a=P[0]=a，符合规则1 → i=3，j=1，next[3]=1

第4轮：i=3，j=1，P[3]=b=P[1]=b，符合规则1 → i=4，j=2，next[4]=2

第5轮：i=4，j=2，P[4]=a=P[2]=a，符合规则1 → i=5，j=3，next[5]=3

第6轮：i=5，j=3，P[5]=c≠P[3]=b，符合规则2 → j=next[3]=1；仍不匹配，j=next[1]=0；仍不匹配，j=next[0]=-1；此时j=-1，符合规则1 → i=6，j=0，next[6]=0

这就是KMP最精妙的设计之一：它用完全自洽的一套逻辑，既完成了next数组的预处理，又完成了主串和模式串的匹配，没有任何多余的设计，算法的美感体现得淋漓尽致。
【代码实现】求next数组

#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 功能：计算模式串P的next数组
// 参数：P - 模式串
// 返回：next数组（vector<int>类型，长度等于P.size()）
vector<int> getNext(const string& P) {
int m = P.size();
vector<int> next(m, 0);

int j = -1; // 前缀指针，初始为-1（哨兵位）
int i = 0;  // 后缀指针，初始为0
next[0] = -1; // 初始化next[0]为-1
while (i < m - 1) {
      // 规则1：j=-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(n+m)的线性时间复杂度的。
还是用之前的案例：

主串S：a b a b a b a c a（下标0-8，长度9）

模式串P：a b a b a c a（下标0-6，长度7）

next数组：[-1, 0, 0, 1, 2, 3, 0]

匹配的核心规则，和next数组的推导逻辑完全一致，同样只有3条：

定义主串指针i=0，模式串指针j=0

当j == -1，或者S == P[j]时：i和j都向后移动一位

当S != P[j]时：令j = next[j]

终止条件：如果j等于模式串的长度m，说明匹配成功，返回起始位置i-j；如果i遍历完主串，j还没到m，说明匹配失败，返回-1

我们一步步走完整个匹配过程：

初始：i=0，j=0

S[0]=a == P[0]=a → i=1，j=1

S[1]=b == P[1]=b → i=2，j=2

S[2]=a == P[2]=a → i=3，j=3

S[3]=b == P[3]=b → i=4，j=4

S[4]=a == P[4]=a → i=5，j=5

S[5]=b ≠ P[5]=c → 匹配失败，j=next[5]=3

此时j=3，S[5]=b == P[3]=b → i=6，j=4

S[6]=a == P[4]=a → i=7，j=5

S[7]=c == P[5]=c → i=8，j=6

S[8]=a == P[6]=a → i=9，j=7

此时j=7，等于模式串的长度7，匹配成功！返回起始位置i-j=9-7=2，也就是主串中从下标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数组
vector<int> next = getNext(P);
int i = 0; // 主串指针，永不回退
int j = 0; // 模式串指针
while (i < n && j < m) {
      // 规则1：j=-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数组。
我们先看一个经典的反例：模式串P=aaaaab，它的next数组是[-1,0,1,2,3,4]。如果主串S=aaabaaaaab，当匹配到S[3]=b和P[3]=a时，匹配失败，j=next[3]=2；此时S[3]=b和P[2]=a还是不匹配，j=next[2]=1；还是不匹配，j=next[1]=0；还是不匹配，j=next[0]=-1。
你看，这里做了4次完全无效的回退——因为P[3]、P[2]、P[1]、P[0]都是a，和P[3]的值完全一样，既然P[3]和主串不匹配，那前面的a肯定也不匹配，这些回退完全是多余的。
所以nextval数组的优化本质，就是消除这些无效的回退：
当我们计算next时，如果P == P[next]，那么我们就把next更新为next[next]，直接跳过上一个相同的字符，避免无效比对。
还是用P=aaaaab，计算它的nextval数组：
模式串下标i012345P字符aaaaabnext-101234nextval-1-1-1-1-14优化后，刚才的匹配失败场景，j会直接从3跳到-1，一步到位，完全消除了无效回退。
【代码实现】优化版nextval数组

// 功能：计算优化后的nextval数组
// 参数：P - 模式串
// 返回：nextval数组
vector<int> getNextval(const string& P) {
int m = P.size();
vector<int> 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数组
vector<int> 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;
}
复制代码
【完整可运行示例】

把所有代码拼在一起，用我们的经典案例测试一下：
[code]int main() { string S = "abababaca"; // 主串 string P = "ababaca"; // 模式串 // 1. 测试基础版KMP int pos = kmpSearch(S, P); cout

账号		自动登录	找回密码
密码			立即注册

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

相关帖子

浏览过的版块

签约作者

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

相关帖子

相关推荐

浏览过的版块

签约作者