Day16 - KMP 算法（理论篇）

文本串 aabaabaaf

模式串 aabaaf

问题：在文本串中aabaabaaf找到模式串aabaaf 的位置

1. 理解暴力算法的痛点

如果使用暴力算法，模式串匹配失败时，会从头开始，文本串也会回退，效率大幅下降。

文本串 aabaabaaf

模式串 aabaaf

当b≠f的时候，匹配失败，文本串从头开始匹配，模式串也会从头开始。

KMP算法的好处：利用已匹配的信息，让模式串跳到正确位置，文本串不后退。

2. 计算模式串的前缀表

前缀表：记录模式串中最长相同前后缀的长度，用于跳过不必要的比较。

模式串 a a b a a f 的前缀表计算：

1.前缀：指不包含最后一个字符的所有子串（如 a, aa, aab,...）

2.后缀：指不包含第一个字符的所有子串（如 f, af, aaf,...）

的比较。

3.最终部分匹配表（通常用 next 数组表示）：

模式串：a a b a a f
next： [0,1,0,1,2,0]

3. 匹配过程（文本串不回头！）

   1. 初始化：文本串指针 i=0 ，模式串 j=0

   2. 逐个比较：

      • 如果 文本[i] == 模式[j]，i 和 j 同时右移。

      • 如果不等，根据 next[j-1] 的值回退 j（文本串 i 不动！）。

   3. 具体步骤：

      文本：a a b a a b a a f
      模式：a a b a a f
      next：[0,1,0,1,2,0]

• 查 next[j-1] = next[4] = 2，表示已匹配部分 aabaa 的最长相同前后缀是 aa（长度2）。

• 所以 j 回退到 2（跳过前缀 aa，直接从 b 开始比）：

  模式回退：a a [b] a a f

• 继续比较 文本[i]=b 和 模式[j=2]=b，匹配！继续后移：

  文本：a a b a a b a a f
  模式：      a a b a a f

• 最终完全匹配，返回起始位置 i - j = 3（即文本中 aabaa 的 第一个a 的位置）。

  • i - j = 9 - 6 = 3

  • 文本串指针 i 会指向匹配结束的下一个位置（即 f 之后）。

  • 模式串指针 j 会指向模式串的末尾（即 j = len(模式串)）。

为什么能跳过？

因为 next 表告诉我们：

• 已匹配的 aabaa 中，后缀 aa 和前缀 aa 相同。

• 所以可以直接把前缀 aa 对齐到后缀 aa 的位置，跳过重复比较。