模拟实现 strstr：从朴素匹配到 KMP

1. 从最自然的实现开始

strstr 的任务很直接：在 haystack 中寻找 needle 第一次完整出现的位置。

如果找到，返回该位置；如果找不到，返回 NULL。

如果暂时完全不考虑更复杂的算法，最自然的做法就是不断假设一个候选起点。

假设：

haystack[i]

可能对应：

needle[0]

那么就从这里开始逐字符向后比较：

haystack[i]     == needle[0]
haystack[i + 1] == needle[1]
haystack[i + 2] == needle[2]
...

如果 needle 全部匹配成功，当前候选起点就是答案。

如果中途失败，则说明：

haystack[i]

不可能是目标子串的起点，于是令候选起点向后移动一位，再重新开始。

这就是朴素匹配。

它的实现简单，而且非常符合 strstr 本身的语义。

但是它存在一个明显的问题：一次匹配可能已经成功比较了很多字符，最后才失败，而失败以后，这些已经得到的信息全部被丢掉。

例如：

haystack: a b a b a b a c
needle:   a b a b a c
          ✓ ✓ ✓ ✓ ✓ ×

前五个字符已经确定相等，最后一个位置才发生失配。

朴素算法此时会重新寻找新的起点，并从 needle[0] 开始重新比较。

于是自然会产生一个问题：

前面已经成功比较过那么多字符，这些信息真的必须全部丢掉吗？

KMP 就是从这个问题开始的。

---

2. 匹配失败以后，哪些信息仍然有价值

上面的失败发生以前，我们已经确定：

haystack 中刚刚成功匹配的部分
==
needle 的某段前缀

例如已经成功匹配：

ababa

那么 haystack 中对应区域的内容也一定是：

ababa

现在观察这段字符串：

ababa

它存在：

前缀：aba
后缀：aba

也就是说，刚才成功匹配区域末尾的：

aba

恰好又等于 needle 开头的：

aba

因此下一轮匹配时，这三个字符其实没有必要重新比较。

可以直接认为：

haystack: a b a b a b a c
needle:       a b a b a c
              ✓ ✓ ✓

前三个字符已经匹配成功。

于是，KMP 真正想利用的并不是一般意义上的“重复块”，而是：

已经匹配成功的部分中，是否存在一个后缀，同时也是 needle 的前缀。

而且这样的部分越长越好，因为能够继承的匹配状态也越多。

---

3. 为什么最后只需要研究 needle

一开始问题似乎是：

haystack 已匹配区域的某个后缀
==
needle 的某个前缀

但实际上不需要重新研究 haystack。

因为刚才已经证明：

haystack 已匹配区域
==
needle 已匹配的前缀

所以 haystack 这一块内部具有什么结构，完全可以通过 needle 自身得到。

于是问题被转化成：

对于 needle 的某一段前缀，它自身最长的“相同前缀和后缀”有多长？

这样就可以提前对 needle 进行一次预处理，把这些信息保存下来。

---

4. LPS 表的定义

设 needle 的长度为 len，其有效字符下标为：

0 ... len - 1

建立数组：

lps[len]

规定：

lps[i]

表示：

在 needle[0..i] 中，最长的“真前缀 = 后缀”的长度。

例如：

needle = a b a b a
         0 1 2 3 4

对于：

needle[0..4] = "ababa"

存在：

前缀：aba
后缀：aba

而且 "aba" 已经是最长的相等前后缀，因此：

lps[4] = 3

如果：

lps[i] = k

那么严格意味着：

needle[0 .. k-1]
==
needle[i-k+1 .. i]

这里必须强调两件事。

第一，前缀必须从 needle[0] 开始。

第二，后缀必须严格结束在 needle[i]。

不能把字符串内部任意一段相同子串都算进来，否则这些信息无法用于后续状态继承。

同时还必须要求是真前缀。

如果允许整个 needle[0..i] 自己和自己比较，那么任何位置都会得到：

lps[i] = i + 1

这样的信息没有任何意义。

---

5. 初始状态

对于：

needle[0]

整个区间只有一个字符。

它不存在非空的真前缀，也不存在能够与之对应的非空真后缀，因此：

lps[0] = 0;

这就是 LPS 构造的初始状态。

从 lps[1] 开始，后面的状态都可以利用之前已经计算出的状态继续推导。

这一点很有动态规划的味道：后面的状态并不是重新从零计算，而是在利用已有结果。

---

6. 从 lps[i-1] 推导 lps[i]

现在准备计算：

lps[i]

假设：

m = lps[i - 1];

那么根据定义，已经知道：

needle[0 .. m-1]
==
needle[i-m .. i-1]

可以把它理解成：

needle[0..i-1]

[ 0 ...... m-1 ] ........ [ i-m ...... i-1 ]
     前缀 m                       后缀 m

现在新加入：

needle[i]

最理想的状态当然是原来的前后缀可以同时向后扩展一位。

左边前缀接下来需要加入的是：

needle[m]

右边后缀新加入的正是：

needle[i]

所以首先只需要检查：

needle[m] == needle[i]

如果成立，那么原来长度为 m 的前后缀成功延长：

lps[i] = m + 1;

真正困难的是两者不相同时怎么办。

---

7. 第一个错误想法：直接归零

如果：

needle[m] != needle[i]

最容易产生的想法就是：

lps[i] = 0;

但这并不成立。

当前失配只能说明：

长度为 m 的这个最长前后缀无法继续延长。

却不能说明：

所有更短的前后缀也都无法延长。

完全可能存在一个更短的前后缀，它的下一个字符恰好等于：

needle[i]

所以不能直接归零。

---

8. 第二个错误方向：不要求后缀结束在当前末尾

另一个自然想法是：

既然 [i] 破坏了原来的状态，是否可以忽略它，继续保留 [0..i-1] 中已有的前后缀？

这样同样不行。

因为我们现在要求的是：

lps[i]

它描述的是整个：

needle[0..i]

的后缀。

后缀按照定义必须结束在：

i

如果允许结束在前面的任意位置，那就已经不再是整个 [0..i] 的后缀，而只是内部某段子串。

更重要的是，这种信息无法用于后面的 KMP 搜索。

KMP 能够继承旧状态的原因，正是因为后缀紧贴在当前已经匹配区域的末端，新的字符可以直接接在它后面。

因此“后缀必须结束在当前末尾”这个条件不能放松。

于是问题变成：

怎样寻找一个更短，但仍然严格结束在 i-1 的合法前后缀？

---

9. 为什么可以查 lps[m-1]

重新回到已经知道的事实：

needle[0 .. m-1]
==
needle[i-m .. i-1]

这两个长度为 m 的区域完全对应相等。

现在设：

n = lps[m - 1];

那么根据定义：

needle[0 .. n-1]
==
needle[m-n .. m-1]

也就是说，在左边长度为 m 的前缀内部，又存在一个更短的长度为 n 的相等前后缀。

而我们已经知道整个长度为 m 的左右两块完全相等，因此左边大块最后 n 个字符：

needle[m-n .. m-1]

也一定等于右边大块最后 n 个字符：

needle[i-n .. i-1]

于是得到：

needle[0 .. n-1]
==
needle[i-n .. i-1]

这说明 n 依旧是 needle[0..i-1] 的一个合法前后缀长度，而且它的后缀仍然紧贴着 i-1。

所以接下来可以继续尝试：

needle[n] == needle[i]

如果相等：

lps[i] = n + 1;

如果仍然不相等，则继续：

n = lps[n - 1];

于是形成一条严格缩短的候选链：

m
↓
lps[m - 1]
↓
lps[lps[m - 1] - 1]
↓
...
↓
0

这不是随便找一个更小的长度，而是在从长到短寻找：

所有仍然严格结束在 i-1 的合法前后缀。

---

10. 从数学递推关系到程序控制逻辑

理解：

m → lps[m - 1]

是一回事。

真正把它写成程序又是另一回事。

算法实现并不是把数学公式翻译成几条赋值语句就结束了，还需要确定：

• 哪些变量表示什么状态；
• 哪些状态需要循环；
• 循环什么时候继续；
• 什么时候退出；
• 退出以后还剩哪些情况没有处理。

对于 lps[i]，程序中最重要的状态变量就是：

m

它始终表示：

当前正在尝试的前后缀长度。

初始化：

size_t m = lps[i - 1];

表示首先尝试上一状态能够提供的最长候选。

现在的问题可以被程序化地重新描述成：

当前长度为 m 的候选
        ↓
needle[m] 能不能和 needle[i] 接上？

如果能：

m → m + 1

当前状态计算结束。

如果不能，则：

m → lps[m - 1]

换一个更短但仍然合法的候选，再继续尝试。

因为一次回退之后仍然可能失败，所以这里不能只使用一次：

if

而需要不断重复：

尝试
↓
失败
↓
回退
↓
再尝试

这自然对应：

while

于是得到：

while (m > 0 && needle[m] != needle[i]) {
    m = lps[m - 1];
}

这里两个循环条件分别有明确含义。

m > 0

表示：

仍然存在一个非空的旧前后缀状态可以继续回退。

而：

needle[m] != needle[i]

表示：

当前候选仍然无法被新字符 [i] 延长。

所以整个 while 的含义就是：

当前候选无法延长，而且仍然存在更短的合法候选时，就继续回退。

---

11. 为什么退出 while 以后还需要一次判断

经过：

while (m > 0 && needle[m] != needle[i]) {
    m = lps[m - 1];
}

以后，循环可能因为两种不同原因结束。

第一种情况是：

needle[m] == needle[i]

说明已经找到了可以延长的候选。

此时：

++m;

即可。

第二种情况是：

m == 0

这里不能立即写：

lps[i] = 0;

因为 m == 0 只表示：

所有旧的非空前后缀候选都已经失败。

但此时仍然存在一种新的可能：

needle[0] == needle[i]

如果成立，那么虽然旧状态全部失败，却可以重新形成长度为 1 的前后缀。

由于现在：

m == 0

所以：

needle[m] == needle[i]

实际上正好就是：

needle[0] == needle[i]

因此退出循环以后统一进行：

if (needle[m] == needle[i]) {
    ++m;
}

即可同时处理：

找到某个更短的旧候选

以及：

全部旧候选失败，但产生长度 1 的新状态

最后：

lps[i] = m;

于是整个 LPS 构造被压缩成：

size_t m = lps[i - 1];

while (m > 0 && needle[m] != needle[i]) {
    m = lps[m - 1];
}

if (needle[m] == needle[i]) {
    ++m;
}

lps[i] = m;

这几行代码虽然很短，但每一行都来自前面的状态分析，并不是需要直接记忆的公式。

---

12. LPS 构造的完整控制过程

把它放回外层循环以后：

lps[0] = 0;

for (size_t i = 1; i < len2; ++i) {
    size_t m = lps[i - 1];

    while (m > 0 && needle[m] != needle[i]) {
        m = lps[m - 1];
    }

    if (needle[m] == needle[i]) {
        ++m;
    }

    lps[i] = m;
}

这里：

i

负责逐步扩大当前研究的 needle 前缀：

needle[0..1]
needle[0..2]
needle[0..3]
...

而：

m

负责在当前前缀内部维护：

当前正在尝试的最长合法前后缀长度。

所以这两个变量承担的职责完全不同。

---

13. 有了 LPS 以后，搜索阶段需要维护什么状态

真正搜索 haystack 时，使用：

size_t i = 0;
size_t j = 0;

其中：

i

表示当前准备处理的 haystack 字符位置。

而：

j

具有两个完全一致的含义：

已经成功匹配的 needle 字符数量

以及：

下一次准备比较的 needle 下标

例如：

j = 3

意味着：

needle[0]
needle[1]
needle[2]

已经匹配成功，下一次应该比较：

needle[3]

正因为“已匹配长度”和“下一下标”在从 0 开始编号时数值相同，所以代码才可以直接使用一个 j 表示这两个状态。

---

14. 字符匹配成功时如何更新状态

如果：

haystack[i] == needle[j]

说明当前这一对字符也匹配成功。

因此：

++i;
++j;

现在：

i

指向 haystack 中下一个尚未处理的字符。

而：

j

表示已经成功匹配的 needle 字符数量。

但这里不能简单结束当前分支。

因为：

++j;

以后可能刚好出现：

j == len2;

这意味着 needle 的最后一个字符刚刚也匹配完成。

也就是说：

完整匹配状态正是在这里产生的。

因此必须立刻检查：

if (j == len2) {
    ...
}

---

15. 为什么完整匹配判断必须放在成功分支内部

这一点看起来只是代码位置问题，实际上非常容易写错。

假设：

haystack = "xxabc"
needle   = "abc"

最后一次比较：

haystack[4] == needle[2]

成功。

随后：

++i;
++j;

得到：

i == 5
j == 3
len2 == 3

所以：

j == len2

完整匹配已经发生。

同时：

haystack[5] == '\0'

如果不在这里立即检查，而是打算等下一轮循环再判断，下一轮首先遇到：

while (haystack[i] != '\0')

条件失败。

循环直接结束。

最后：

return NULL;

于是会出现：

明明刚刚已经完整匹配，却因为匹配终点恰好也是 haystack 的终点，成功状态没有得到处理。

所以成功状态必须在产生以后立即捕获。

---

16. 为什么不能把 j == len2 随便塞进失配分支链

还存在另一个问题。

假设把代码写成类似：

if (haystack[i] == needle[j]) {
    ++i;
    ++j;
}
else if (j > 0) {
    j = lps[j - 1];
}
else if (j == len2) {
    ...
}

这同样错误。

因为：

j == len2

一定同时满足：

j > 0

也就是说，“完整匹配成功”状态和“存在部分历史匹配”状态发生条件重叠。

如果控制顺序不正确，已经完整匹配成功的状态反而可能被：

j = lps[j - 1];

回退掉。

更根本的问题在于：

j == len2

本来就不是一种“失配状态”。

它是：

一次字符匹配成功以后产生的完成状态。

所以控制结构本身应该具有层级：

本次字符比较
│
├─ 成功
│   │
│   ├─ i++
│   ├─ j++
│   │
│   └─ j == len2 ?
│       ├─ 是：完整匹配，立即返回
│       └─ 否：继续
│
└─ 失败
    │
    ├─ j > 0
    │   └─ 回退 j
    │
    └─ j == 0
        └─ 前进 i

这样控制流才与算法状态完全一致。

---

17. 完整匹配以后怎样得到起点

当：

j == len2

成立时，j 表示已经完整匹配的字符数量。

同时：

i

已经因为最后一次成功匹配而前进到了匹配区域之后。

例如：

haystack: x x a b c
          0 1 2 3 4

needle:     a b c

完整匹配以后：

i = 5
j = 3

所以匹配起点就是：

5 - 3 = 2

即：

haystack + (i - j)

因此完整处理为：

if (j == len2) {
    free(lps);
    return (char*)haystack + (i - j);
}

这个位置既能及时捕获成功状态，也可以直接利用当前 i、j 算出目标起点。

---

18. 失配以后为什么只回退 j

如果：

haystack[i] != needle[j]

但：

j > 0

说明前面：

needle[0 .. j-1]

已经成功匹配。

因此查：

lps[j - 1]

就可以知道这 j 个已匹配字符中，还有多长的前缀状态能够继续继承。

所以：

j = lps[j - 1];

这里有一个极其重要的实现细节：

i

不能移动。

因为当前：

haystack[i]

只证明：

haystack[i] != 旧 needle[j]

但没有证明：

haystack[i] != 回退后的新 needle[j]

当前字符仍然可能成为新状态下的下一个匹配字符。

因此失配但 j > 0 时只能改变：

j

不能：

++i;

---

19. 什么时候才能移动 i

只有当：

j == 0

同时：

haystack[i] != needle[0]

时，才说明：

当前 haystack[i] 连 needle 的第一个字符都无法匹配，因此它不可能再属于任何以当前状态为基础的候选匹配。

这时才可以：

++i;

所以搜索主体最终形成三个状态：

if (haystack[i] == needle[j]) {
    ++i;
    ++j;

    if (j == len2) {
        free(lps);
        return (char*)haystack + (i - j);
    }
}
else if (j > 0) {
    j = lps[j - 1];
}
else {
    ++i;
}

现在这段代码可以直接按状态解释：

匹配成功
→ 双方前进
→ 检查是否完成

匹配失败但有历史状态
→ 只回退 needle

匹配失败且已经无状态可退
→ 丢弃当前 haystack 字符

---

20. KMP 真正避免了什么

KMP 并不是让 haystack 一次跳过很多字符。

事实上：

i

基本仍然是逐字符向前移动。

真正重要的是：

i 永远不会回退。

朴素算法在一次深度匹配失败以后，会把候选起点向后移动，再重新读取之前已经比较过的 haystack 字符。

KMP 则保留：

haystack 当前扫描位置

只通过：

j = lps[j - 1];

改变：

needle 当前匹配状态

所以之前已经确认过的信息不会被全部丢掉。

---

21. 为什么不断回退仍然是线性复杂度

设：

• haystack 长度为 n；
• needle 长度为 m。

搜索阶段中，j 虽然可能反复回退，但每一次：

++j;

一定伴随：

++i;

因此 j 的累计增长量受到 i 的累计增长量限制。

而 i 最多前进 n 次。

另一方面：

j = lps[j - 1];

每次都会让 j 严格减小。

所以所有回退都只是在消耗此前已经积累出来的匹配长度。

因此搜索阶段总复杂度为：

$$O(n)$$

LPS 的构造过程同样使用这种“增长 + 严格回退”的结构，所以复杂度为：

$$O(m)$$

最终：

$$O(n+m)$$

这里使用的是摊还分析的思想，并不是要求每一次循环都只执行固定数量的操作。

---

22. 理论复杂度更好，不代表实际一定更快

KMP 的最坏复杂度为：

$$O(n+m)$$

而朴素算法最坏可能达到：

$$O(nm)$$

但这并不意味着实际使用中 KMP 一定更快。

普通字符串中，大量候选位置往往在第一个或前几个字符就会失败。

例如：

haystack = 普通文本
needle   = xyz...

很多候选位置实际上只需要比较一次：

haystack[i] != 'x'

就结束。

此时朴素算法虽然最坏复杂度仍然是 O(nm)，实际工作量却可能接近一次线性扫描，而且：

没有 LPS
没有额外预处理
没有状态回退
控制逻辑更加简单

因此常数开销可能更低。

而高度重复的数据：

haystack = aaaaaaaaaaaaaaaaa...
needle   = aaaaaaaab

则可能让每个候选位置都进行大量比较以后才失败。

这时 KMP 的优势会迅速扩大。

---

23. 曾尝试使用经验系数自动选择算法

曾经尝试使用：

$$\frac{(n-m+1)m}{n+m}$$

估计朴素算法与 KMP 的工作量关系，并希望找到一个经验系数 K：

score <= K
    → naive

score > K
    → KMP

但实际 benchmark 表明，这种模型无法可靠工作。

例如：

n = 256
m = 64
score = 38.60

普通数据：

fast-miss:
naive ≈ 196 ns
KMP   ≈ 448 ns

朴素算法更快。

而高度重复数据：

repeat-miss:
naive ≈ 5485 ns
KMP   ≈ 937 ns

KMP 又明显更快。

也就是说：

n 相同
m 相同
score 相同

最优算法仍然可能完全相反。

真正影响朴素算法工作量的是：

每个候选位置实际能够向后匹配多深才失败。

更接近其真实工作量的描述应该是：

$$\sum L_s$$

其中 L_s 表示候选起点 s 实际进行了多少次字符比较。

而仅仅知道 n 和 m 无法得到这些信息。

因此最终放弃使用单一经验系数进行所谓的自动智能分流。

---

24. 最终实现策略

最终选择：

默认使用朴素算法，需要时显式启用 KMP。

这并不是认为朴素算法在理论上优于 KMP，而是因为对于当前 strstr 模拟实现：

• 朴素算法直接表达函数语义；
• 普通数据下常数开销较低；
• KMP 主要提供更好的最坏情况保证；
• 单纯根据字符串长度无法可靠预测两者实际性能。

因此 KMP 作为一个可选实现保留。

---

25. 公共接口与内部实现职责

对外只希望暴露：

myStrstr(...)

而：

naiveStrstr(...)
kmpStrstr(...)

只是实现细节。

因此二者不进入公开头文件，并可以在实现文件中声明为：

static

公共入口统一完成：

strlen

以及：

if (len2 == 0)
    return (char*)haystack;

if (len2 > len1)
    return NULL;

这些属于 strstr 本身的公共语义，不属于某一种具体搜索算法。

这样不需要在 naive 和 KMP 内部分别复制同样的边界处理。

---

26. 为什么 main.c 中的宏不能直接影响另一个 .c 文件

希望使用：

#define USE_KMP_STRSTR

直接在调用方选择 KMP。

但是如果 myStrstr 的实现位于另一个 .c 文件中，那么：

#define USE_KMP_STRSTR

只影响当前翻译单元。

例如：

main.c
strstr.c

在：

main.c

中定义的宏不会自动传播给：

strstr.c

所以不能简单在 strstr.c 中写：

#ifdef USE_KMP_STRSTR

并期待 main.c 中的宏能够控制它。

---

27. 通过宏包装公开调用

为了仍然允许调用者写：

#define USE_KMP_STRSTR
#include "..."

来控制算法，可以让宏控制“调用方式”，而不是控制另一个翻译单元的编译过程。

例如头文件：

#ifdef USE_KMP_STRSTR

#define myStrstr(haystack, needle) \
    myStrstrImpl((haystack), (needle), true)

#else

#define myStrstr(haystack, needle) \
    myStrstrImpl((haystack), (needle), false)

#endif

真实入口：

char* myStrstrImpl(
    const char* haystack,
    const char* needle,
    bool useKmp
);

内部统一处理边界条件以后：

if (useKmp) {
    return kmpStrstr(
        haystack,
        len1,
        needle,
        len2
    );
}

return naiveStrstr(
    haystack,
    len1,
    needle,
    len2
);

这样：

#define USE_KMP_STRSTR
#include "..."

时：

myStrstr(...)

自动走 KMP。

没有定义宏时，则默认走朴素实现。

宏必须位于相关头文件之前，因为选择过程发生在预处理阶段。

---

28. 最终理解

这次实现 strstr，真正值得保留下来的并不是某张 next 表，也不是：

m = lps[m - 1];

这种看起来精巧的代码本身。

更重要的是完整的推导过程：

朴素算法深度匹配失败
↓
发现已经取得的信息被全部浪费
↓
寻找能够继续继承的匹配状态
↓
得到“已匹配后缀 = needle 前缀”
↓
利用已匹配内容本身等于 needle 前缀
↓
把问题完全转化成研究 needle 自身
↓
定义 LPS
↓
最长状态延长失败时发现不能直接归零
↓
要求更短候选仍然紧贴当前末尾
↓
利用已知相等的大前后缀
↓
自然推出 lps[m - 1] 回退链
↓
再把数学状态转化成 m 的 while 控制过程
↓
搜索阶段用 j 表示“已匹配长度 / 下一 needle 下标”
↓
失配时只回退 j，不回退 i
↓
成功后立即检查 j == len2
↓
在完成状态产生的瞬间捕获结果

所以 KMP 的难点实际上有两层。

第一层是：

怎样把“匹配失败以后哪些信息仍然有效”抽象成前后缀数学模型。

第二层是：

怎样把这个数学模型准确地转换成变量状态、循环条件和分支控制，而不在边界状态上丢失信息。

后者尤其容易被最终只有几行的代码掩盖。

KMP 的核心思想最终可以概括为：

一次失败只否定当前候选状态，并不意味着此前已经获得的全部信息都失效。

而实现层面的核心则是：

每一种状态都必须在它产生的正确时刻被处理，不能只知道数学关系，却忽略控制流中的状态生命周期。