在长文本轨道中锁定第一段目标指纹

字符串 · KMP / 失败函数

暴力法失败后会回头重试;KMP 用 LPS 记住模式串内部结构,让文本指针 i 永远向前。本页把 i / j / lps / 失配跳转这四件事画清楚。

当前输入

haystack"aabaabaafa"n=10

needle"aabaaf"m=6

KMP 最终返回

锁定 haystack[3..8]

暴力法时间 O(n · m) · 空间 O(1)

失配回退,字符被反复比较

KMP时间 O(n + m) · 空间 O(m)

lps 数组占 O(m),i 永不回退

边界测试 · 切换后整段动画会重算

题目输入Step 1/12

当前发生了什么

Scene 1 · 题目输入

在 haystack = "aabaabaafa" 中找 needle = "aabaaf" 第一次出现的下标。找不到返回 -1。

haystack 长度 n=10 · needle 长度 m=6

机器状态

haystack[i]: —
needle[j]: —
i − j (模板起点): —
已匹配长度 = j: —

指纹扫描舞台

i = — · j = — · 已匹配 = —

i 文本扫描光标j 模板内部指针已匹配 / 命中失配锁定区间

LPS 失败跳转地图

还没引入 LPS。先理解暴力法的代价,再回来看这张表。

代码同步 · Go

题目输入

1func strStr(haystack, needle string) int {
2    n, m := len(haystack), len(needle)
3    if m == 0 { return 0 }
4    lps := buildLPS(needle)
5    i, j := 0, 0
6    for i < n {
7        if haystack[i] == needle[j] {
8            i++; j++
9        } else if j > 0 {
10            j = lps[j-1]   // i 不动,j 跳
11        } else {
12            i++
13        }
14        if j == m {
15            return i - j
16        }
17    }
18    return -1
19}

展开 buildLPS(needle) 子函数

1func buildLPS(s string) []int {
2    m := len(s)
3    lps := make([]int, m)
4    length, i := 0, 1
5    for i < m {
6        if s[i] == s[length] {
7            length++; lps[i] = length; i++
8        } else if length != 0 {
9            length = lps[length-1]
10        } else {
11            lps[i] = 0; i++
12        }
13    }
14    return lps
15}

循环不变量

还没开始扫描,i = 0,j = 0。

为什么这一步是对的

这是一个朴素的子串匹配:haystack 是横向轨道,needle 是要套上去的模板。

面试该怎么说 · LC28 是 strStr,要求实现 indexOf;允许用库就一行,不允许就上 KMP。

12 步剧本时间线

暴力 vs KMP 对照 · 同一组输入,看 i 会不会回退

1 / 19 · action = compare-match

从 i=0 起对齐,haystack[0]='a' 等于 needle[0]='a'。

关键差异 · 暴力法每次失配都把 i 推到下一个起点并把 j 清零 ——同一个 haystack 字符可能被对比 m 次。

面试 · 一段话讲清楚

LC28 可以暴力做,但如果要求不用库函数且追求线性复杂度,使用 KMP。先对 needle 构建 lps: lps[i] 是 needle[0..i] 的最长相等真前后缀长度;再扫描 haystack:匹配时 i、j 同进,失配时 j = lps[j-1], i 不回退; 当 j 达到 m 立即 return i − j。总时间 O(n + m),空间 O(m)(lps 数组)。

常见误区

✗ 把 lps 当成“匹配位置”——它记录的是 needle 当前前缀内部可复用的最长前后缀长度。
✗ KMP 失配时移动 i——错。失配时只移动 j,i 单调向前。
✗ 一上来就让 i++。只有 j == 0 且 haystack[i] ≠ needle[0] 才让 i++。
✗ 把 KMP 的空间复杂度说成 O(1)。lps 数组长度等于 m,所以是 O(m)。