第 288 题：字符串匹配的KMP算法？prefix function？
题目
字符串匹配的KMP算法？prefix function？
完整讲解
一、KMP 目的
| 在文本 T 中找模式 P 的首次出现，线性时间 O( |
T |
+ |
P |
)。朴素匹配在失配时只移 1 位；KMP 利用「已匹配部分」的信息，一次滑动多位，且不回溯 T 的指针。 |
二、Prefix function（next 数组）
前缀函数 π[i]：P[0..i] 的真后缀与 P 的真前缀的最长匹配长度。即 π[i] = max{k : P[0..k-1] = P[i-k+1..i], k < i+1}。求法：用递推，若 P[i]=P[π[i-1]] 则 π[i]=π[i-1]+1，否则用 π[π[i-1]-1] 递归尝试。next 数组 常指「失配时 P 应移动到的下标」：next[j] = π[j-1]（或按实现略有偏移），表示在 j 处失配时，用 next[j] 作为 P 的新对齐位置（T 指针不回溯）。
三、匹配过程
T 与 P 从左对齐，逐位比较；失配时 T 指针不动，P 按 next 右移（即 P 的 next[j] 与当前 T 位置对齐），继续比较。构造 next 与匹配均为 O(n)。
面试要点
- KMP：线性时间字符串匹配；失配时 P 按 next 右移、T 不回溯。
- 前缀函数 π[i]：P[0..i] 的真后缀与真前缀的最长匹配；递推可求。
- next[j]：j 处失配时 P 应对齐的下标；用 π 得到。
-
| 构造 next O( |
P |
)、匹配 O( |
T |
)。 |
记忆要点
- 前缀函数 = 真后缀与真前缀最长匹配；递推求 next。
- 失配时 T 不动、P 按 next 右移。
-