ARTICLE DETAIL

建站实战干货

来自一线的建站与推广经验沉淀，每一条都经过真实交付验证。

首页 / 资讯中心 / 正文

KMP算法详解：从暴力匹配到线性时间复杂度的字符串查找

2026/8/15 23:23:43 拓冰建站 浏览量
KMP算法详解：从暴力匹配到线性时间复杂度的字符串查找

1. 从“暴力匹配”的困境说起

如果你写过字符串查找的代码，大概率是从一个简单的双重循环开始的：外层循环遍历主串的每个位置作为起始点，内层循环逐个字符与模式串进行比较。一旦发现不匹配，外层循环就跳到下一个位置，模式串从头再来。这就是所谓的“暴力匹配”（Brute-Force）。它的逻辑直观，代码简单，但效率是硬伤。假设主串长度为n，模式串长度为m，最坏情况下（比如主串是“aaaaaaaaab”，模式串是“aaab”），时间复杂度会达到O(n*m)。当处理大量文本数据时，这种性能开销是难以接受的。

问题的核心在于“回溯”。每次匹配失败，主串的指针（我们称之为i）和模式串的指针（j）都要回退。i回退到本轮起始位置的下一个点，j则直接归零。这意味着之前已经比较过的、可能包含有效信息的字符被完全丢弃了，下一次匹配又从头开始“盲猜”，做了大量重复且无效的比较。

那么，有没有一种方法，能在匹配失败时，利用已经匹配成功的那部分前缀信息，让模式串“智能地”滑动一段距离，同时主串指针i绝不后退，从而避免重复劳动呢？这就是KMP算法要解决的核心问题。它通过一个神奇的“部分匹配表”（常被称为next数组），将模式串的自我匹配信息预先计算好，在匹配失败时指导j指针进行精确回退，实现了O(n+m)的线性时间复杂度。今天，我们就来彻底拆解这个被誉为字符串匹配领域里程碑的算法，不仅看懂它怎么工作，更要理解它为什么这样设计。

2. KMP的核心：理解“最长相等前后缀”与next数组

KMP算法的精髓，完全蕴含在那个预先计算的next数组里。要理解next数组，必须先理解一个关键概念：最长相等前后缀。

对于一个字符串"ababc"：

  • 前缀集合："a","ab","aba","abab"
  • 后缀集合："c","bc","abc","babc"
  • 注意，前后缀都不包括字符串本身。

所谓“最长相等前后缀”，就是找出一个字符串中，相等的、最长的那个前缀和后缀的长度。对于"ababc"：

  • 长度为1：前缀"a"，后缀"c"，不相等。
  • 长度为2：前缀"ab"，后缀"bc"，不相等。
  • 长度为3：前缀"aba"，后缀"abc"，不相等。
  • 长度为4：前缀"abab"，后缀"babc"，不相等。 所以，"ababc"的最长相等前后缀长度为0。

再看"abab"：

  • 长度为1："a"vs"b"，不等。
  • 长度为2："ab"vs"ab"，相等！长度为2。
  • 长度为3："aba"vs"bab"，不等。 因此，"abab"的最长相等前后缀长度为2。

next数组的定义：对于模式串P，next[j]表示子串P[0...j-1]（即模式串中从开头到第j-1个字符构成的子串）的“最长相等前后缀”的长度。这里有一个关键点，也是初学者最容易混淆的地方：next[j]的值对应的是已匹配前缀的下一个匹配位置，或者说，当在P[j]处匹配失败时，j应该回退到的新位置。

更具体一点：假设我们在模式串的第j位（从0开始计数）匹配失败了。那么，我们已经成功匹配了j个字符，即子串P[0...j-1]。这个子串的最长相等前后缀长度，假设为k。这意味着这个子串的前k个字符（P[0...k-1]）和后k个字符（P[j-k...j-1]）是完全一样的。既然主串中与P[j-k...j-1]对齐的部分已经匹配成功（因为整个P[0...j-1]都匹配了），那么它必然也和P[0...k-1]一样。所以，我们可以直接把模式串向右滑动，让P[0]对齐到主串中原来与P[j-k]对齐的位置，并且可以确信，P[0...k-1]这一段无需再比较，一定是匹配的。接下来，我们只需要从模式串的P[k]位置开始，与主串当前指针i继续比较即可。

因此，next[j]的实际作用就是：当模式串P在第j个字符匹配失败时，j指针应该跳转到的下一个比较位置。通常我们令j = next[j]。特别的，我们规定next[0] = -1，这表示如果模式串的第一个字符就不匹配，那么模式串整体右移一位，主串指针i前进，j从0开始（通过j = next[0] + 1实现）。

注意：next数组有不同的定义版本，有的版本next[j]直接表示跳转后的索引（此时next[0] = -1），有的版本表示长度值（此时next[0] = 0）。本文采用前一种更常见的定义，因为它与代码中的回退操作j = next[j]直接对应，逻辑更清晰。

3. 手动推导next数组：以“ababc”为例

理论可能有些抽象，我们通过一个完整的例子来亲手计算一遍。设模式串P = "ababc"。

  1. j = 0: 子串为空，我们规定next[0] = -1。
  2. j = 1: 子串为"a"。一个字符的字符串，没有真前缀和真后缀（因为不能是自身），所以最长相等前后缀长度为0。根据我们的定义，next[1] = 0。（这意味着，如果在P[1]（即'b'）匹配失败，j应回退到0，即从P[0]（'a'）开始比较）。
  3. j = 2: 子串为"ab"。
    • 长度为1的前缀："a"，后缀："b"，不相等。
    • 最长相等前后缀长度为0。所以next[2] = 0。
  4. j = 3: 子串为"aba"。
    • 长度为1：前缀"a"，后缀"a"，相等。
    • 长度为2：前缀"ab"，后缀"ba"，不相等。
    • 最长相等前后缀长度为1。所以next[3] = 1。（如果在P[3]（即第二个'a'）失败，j回退到1，即P[1]（'b'））。
  5. j = 4: 子串为"abab"。
    • 长度为1："a"vs"b"，不等。
    • 长度为2："ab"vs"ab"，相等。
    • 长度为3："aba"vs"bab"，不等。
    • 最长相等前后缀长度为2。所以next[4] = 2。

最终得到的next数组为：[-1, 0, 0, 1, 2]。

这个计算过程是理解的基础，但在实际代码中，我们不会每次都去截取子串再比较前后缀，那样效率太低。KMP算法的高明之处在于，next数组的求解本身也是一个“字符串匹配”过程，模式串既是主串也是模式串，我们可以用类似动态规划的思想，在O(m)的时间内完成计算。

4. next数组的高效构建算法

构建next数组的算法是KMP学习的第二个难点。其核心思想是“递推”和“自我匹配”。

我们定义两个指针：i和j（在构建next数组的语境下，为了避免混淆，有些资料会用i和k）。这里我们统一用i和j，但请注意，此处的i指向的是当前要计算next值的位置（即“主串”指针），而j指向前缀的末尾（即“模式串”指针），同时j也代表了next[i]的候选值。

算法步骤如下：

  1. 初始化：next[0] = -1。令i = 0,j = -1。
  2. 循环，当i < m-1时（m为模式串长度）： a. 如果j == -1或者P[i] == P[j]，则i++,j++，然后设置next[i] = j。 -j == -1是边界条件，意味着要重新开始匹配前缀。 -P[i] == P[j]意味着在当前位置，前缀和后缀可以扩展一位，所以最长相等前后缀长度增加1。 b. 否则（即P[i] != P[j]），令j = next[j]。 - 这一步是精髓！它利用已经计算好的next值进行回溯，避免了j直接归零的暴力回溯，和主匹配过程的思想完全一致。

让我们用模式串"ababc"来走一遍这个过程，m=5。

  • 初始化：next[0] = -1,i=0,j=-1。
  • 第1轮：i=0，j=-1，满足j == -1。执行i++(1),j++(0)，设置next[1] = j = 0。
  • 第2轮：i=1，j=0，比较P[1]('b')和P[0]('a')，不相等。执行j = next[0] = -1。
  • 第3轮：i=1，j=-1，满足j == -1。执行i++(2),j++(0)，设置next[2] = j = 0。
  • 第4轮：i=2，j=0，比较P[2]('a')和P[0]('a')，相等！执行i++(3),j++(1)，设置next[3] = j = 1。
  • 第5轮：i=3，j=1，比较P[3]('b')和P[1]('b')，相等！执行i++(4),j++(2)，设置next[4] = j = 2。
  • 循环结束（i=4，不小于m-1=4）。

得到next = [-1, 0, 0, 1, 2]，与手动推导一致。这个过程的时间复杂度是O(m)。

实操心得：理解这个构建过程的关键在于，把P[0...j]看作已匹配的“前缀”，P[i-j...i]看作正在考察的“后缀”。当P[i]和P[j]相等时，前后缀可以同步延长；不相等时，就利用已知的next信息，将前缀指针j回退到一个可能匹配的位置，而不是傻傻地回到开头。这其实就是KMP主算法的一个“预演”。

5. 主匹配流程详解与代码实现

有了next数组，主匹配过程就非常清晰了。我们设主串为S，模式串为P，长度分别为n和m。指针i遍历主串，指针j遍历模式串。

匹配过程：

  1. 初始化i = 0,j = 0。
  2. 循环，当i < n且j < m时： a. 如果j == -1或者S[i] == P[j]，则i++,j++。 -j == -1表示模式串已经滑到最左边，需要将主串指针和模式串指针都向前推进一位。 - 字符相等，自然双双后移。 b. 否则（即S[i] != P[j]且j != -1），令j = next[j]。 - 这就是KMP的“跳跃”精髓。利用next数组，j回退，i不动。
  3. 循环结束后，判断：
    • 如果j == m，说明模式串完全匹配，返回匹配起始位置i - j。
    • 否则，匹配失败，返回-1。

下面是用Python实现的完整KMP算法：

def kmp_search(main_string, pattern): """ KMP字符串匹配算法 :param main_string: 主串 :param pattern: 模式串 :return: 模式串在主串中首次出现的索引，未找到返回-1 """ def build_next(p): """构建next数组""" m = len(p) next_arr = [-1] * m # 初始化next数组 i, j = 0, -1 # i是后缀末尾，j是前缀末尾，也代表next[i]的值 while i < m - 1: # 注意循环条件，因为next[i]是看P[0...i-1] if j == -1 or p[i] == p[j]: i += 1 j += 1 # 这里是一个可以优化的点，见后续章节 next_arr[i] = j else: j = next_arr[j] # 前缀指针回溯 return next_arr n, m = len(main_string), len(pattern) if m == 0: return 0 # 空模式串约定俗成返回0 if n < m: return -1 next_arr = build_next(pattern) i, j = 0, 0 # i主串指针，j模式串指针 while i < n and j < m: if j == -1 or main_string[i] == pattern[j]: # 匹配成功，或j已在最左端，双指针右移 i += 1 j += 1 else: # 匹配失败，根据next数组移动模式串指针 j = next_arr[j] # 匹配成功判断 if j == m: return i - j else: return -1 # 测试 if __name__ == "__main__": s = "BBC ABCDAB ABCDABCDABDE" p = "ABCDABD" pos = kmp_search(s, p) print(f"在主串 '{s}' 中查找模式串 '{p}'") print(f"首次出现位置（从0开始）: {pos}") # 输出: 首次出现位置（从0开始）: 15 # 更多测试 print(kmp_search("hello", "ll")) # 2 print(kmp_search("aaaaa", "bba")) # -1 print(kmp_search("", "")) # 0 print(kmp_search("a", "")) # 0

让我们用经典的例子S="BBC ABCDAB ABCDABCDABDE",P="ABCDABD"来模拟一下。首先计算P的next数组为[-1, 0, 0, 0, 0, 1, 2]。

匹配过程关键点：

  1. 初始i=0, j=0，S[0]='B',P[0]='A'，不匹配，j = next[0] = -1。
  2. j == -1，执行i++(1),j++(0)。
  3. ... 跳过若干步，直到i=4, j=0（S[4]='A',P[0]='A'），开始匹配。
  4. 一路匹配到i=10, j=6（此时已匹配"ABCDAB"），S[10]=' ',P[6]='D'，不匹配。
  5. 关键跳跃：j = next[6] = 2。这意味着我们已经匹配的"AB"（P[0-1]）可以作为下一轮匹配的前缀，i保持不变（i=10），j从2（即P[2]='C'）开始比较。
  6. 此时S[10]=' ',P[2]='C'，不匹配，j = next[2] = 0。
  7. S[10]=' ',P[0]='A'，不匹配，j = next[0] = -1。
  8. j == -1，执行i++(11),j++(0)。
  9. ... 最终在i=15, j=0处重新开始，并成功匹配到i=22, j=7，匹配成功。

整个过程，主串指针i从未回退，一直向前，这正是KMP高效的原因。

6. next数组的优化：nextval数组

细心的你可能已经发现，上述标准KMP算法还有优化空间。看这个例子：模式串P="AAAAAB"，其next数组为[-1, 0, 1, 2, 3, 4]。假设在主串S="AAAAAAC..."中匹配。

当i=5, j=5时（已匹配"AAAAA"），S[5]='C',P[5]='B'，不匹配。根据next数组，j = next[5] = 4。然后比较S[5]='C'和P[4]='A'，不匹配。j = next[4] = 3，再比较S[5]='C'和P[3]='A'... 你会发现，由于P[4]、P[3]、P[2]、P[1]、P[0]都是'A'，且都与S[5]='C'不匹配，所以j会按照4 -> 3 -> 2 -> 1 -> 0 -> -1的路径一步步回退，做了多次无意义的比较。

问题的根源在于：当P[j] != S[i]时，我们跳到了next[j]，但如果P[next[j]] == P[j]，那么这次跳跃后的比较S[i]和P[next[j]]必然还是会失败，因为P[j]已经和S[i]比较过且不相等，而P[next[j]]和P[j]相同。既然如此，我们何不一步到位，直接跳到第一个与P[j]不同的字符位置呢？

这就是nextval数组的优化思想。它在构建next数组的过程中，额外增加一次判断：

  • 如果P[i] == P[next[i]]，那么nextval[i] = nextval[next[i]]（因为回退后比较的字符相同，必然再次失败，所以用更早的回退值）。
  • 否则，nextval[i] = next[i]。

优化后的构建函数如下：

def build_next_val(p): """构建优化后的nextval数组""" m = len(p) next_val = [-1] * m i, j = 0, -1 while i < m - 1: if j == -1 or p[i] == p[j]: i += 1 j += 1 # 优化点：如果回退后的字符与当前字符相同，则继续回退 if p[i] == p[j]: next_val[i] = next_val[j] else: next_val[i] = j else: j = next_val[j] return next_val

对于P="AAAAAB"：

  • 标准next:[-1, 0, 1, 2, 3, 4]
  • 优化nextval:[-1, -1, -1, -1, -1, 4]

在刚才的例子中，当j=5匹配失败时，j = nextval[5] = 4。但此时我们发现P[5]('B') != P[4]('A')，所以nextval[4]没有因为相等而被优化，仍是-1？等等，让我们仔细计算一下nextval[4]。根据规则，在计算nextval[4]时，i=4, j=3，P[4]('A') == P[3]('A')，所以nextval[4] = nextval[3]。递归地，nextval[3] = nextval[2],nextval[2] = nextval[1],nextval[1] = nextval[0] = -1。所以最终nextval[4] = -1。因此，当j=5失败跳转到4后，紧接着j = nextval[4] = -1，直接跳过了中间所有相同的'A'，效率大幅提升。

在实际应用中，特别是模式串中有大量重复字符时，使用nextval数组可以进一步提升匹配效率。它并没有改变算法的时间复杂度上界（依然是O(n+m)），但减少了常数因子，是KMP算法一个非常经典的优化。

7. 复杂度分析与KMP的适用场景

时间复杂度：

  • 构建next（或nextval）数组：O(m)，其中m是模式串长度。这个过程只遍历模式串常数次。
  • 主匹配过程：O(n)，其中n是主串长度。虽然主串指针i可能在某些轮次不增加（当发生失配且j != -1时），但i从不减少，而j的变化（增加或通过next数组减少）是与i的增加相关联的。j增加的总次数不会超过n（因为每次i增加j才可能增加），而j通过next数组减少的总次数也不会超过j增加的总次数（因为j必须非负）。因此，整个主匹配过程是线性的。
  • 总时间复杂度：O(n + m)。

空间复杂度：主要是next数组，O(m)。

KMP算法的适用场景与局限：

  • 优势场景：
    1. 主串和模式串都非常长，且匹配失败经常发生在模式串的靠后位置。此时KMP避免主串回溯的优势非常明显。
    2. 需要多次用同一个模式串匹配不同的主串。next数组只需计算一次，即可重复使用，摊销了预处理成本。
    3. 流式数据匹配。因为主串指针i不回溯，所以可以处理无法随机访问或只能单向读取的数据流（如网络数据包、实时日志流），这是暴力算法无法做到的。
  • 局限与权衡：
    1. 实现复杂度：比暴力算法复杂得多，理解和实现都有一定门槛。
    2. 常数因子：虽然时间复杂度优，但涉及额外的数组访问和判断，在模式串很短、主串不长，或者匹配往往在模式串开头就失败的情况下，其实际运行速度可能不如高度优化的暴力算法（例如使用系统库的memcmp或strstr）。
    3. 内存开销：需要额外的O(m)空间存储next数组。对于极长的模式串（例如上百万字符），这可能是个问题。
    4. 并非所有情况都最快：在实际的字符串搜索库（如Python的find、C的strstr）中，通常采用更复杂的混合算法（如Boyer-Moore、Sunday算法等），这些算法在平均情况下往往比KMP更快，因为它们利用了“坏字符”规则进行更大幅度的跳跃。KMP的优势在于最坏情况下的线性保证。

因此，在一般的应用开发中，我们通常直接使用语言内置的字符串查找函数。但在一些特殊的底层系统、文本编辑器、生物信息学（DNA序列匹配）或算法竞赛中，理解并能够实现KMP算法仍然是一项重要的技能。

8. 从KMP到更广阔的字符串匹配世界

KMP算法是理解现代字符串匹配算法的一把钥匙。它引入了“利用已匹配信息避免回溯”的核心思想，启发了后续许多算法。

  • Boyer-Moore (BM) 算法：它采用了两种启发式规则——“坏字符规则”和“好后缀规则”，从模式串的末尾开始向前匹配。当发生不匹配时，它可以根据这两个规则计算出更大的滑动距离，在实践中平均性能往往优于KMP，特别是在字符集较大（如英文文本）时。不过，它的最坏情况时间复杂度可能是O(n*m)。
  • Sunday 算法：可以看作是BM算法“坏字符规则”的一个简化且高效的变种。它关注的是主串中参与匹配的窗口的下一个字符（即“周日字符”），根据这个字符在模式串中的位置进行跳跃。实现简单，且在实际应用中通常有很好的效果。
  • Aho-Corasick (AC) 自动机：可以看作是KMP算法在多模式匹配场景下的扩展。它能够同时搜索多个模式串，其核心数据结构（Trie树加上失败指针）的思想与KMP的next数组一脉相承。失败指针的作用就是在某个节点匹配失败时，跳转到另一个可能的最长匹配前缀节点，这正是KMP思想在多模式下的体现。
  • Rabin-Karp 算法：采用了完全不同的思路——哈希。它计算模式串的哈希值，以及主串中每个等长子串的哈希值，通过比较哈希值来快速筛选可能匹配的位置。虽然需要处理哈希冲突，但其思路简单，且在某些场景下（如二维模式匹配）有优势。

理解KMP，不仅仅是学会了一个算法，更是掌握了一种“预处理模式串以加速匹配”的范式。当你下次遇到需要高效处理字符串匹配的问题时，无论是单模式还是多模式，是精确匹配还是近似匹配，你都能从KMP所代表的这种“空间换时间”、“利用历史信息”的思想中找到灵感。