LeetCode 28. 找出字符串中第一个匹配项的下标
题目描述
题意分析
在文本
haystack中寻找与模式串needle完全相同的连续片段，返回最小起始下标；不存在则返回-1。逐个起点重新比较会反复检查已经匹配的字符。KMP 先整理模式串自身的前后缀关系，失配时复用已匹配部分，让文本下标始终向前。
解法：KMP 前缀表匹配
核心思路
[!blue]
扫描文本时，
matched表示已经处理的文本末尾，与模式串开头相同的最长长度。所以下一个文本字符haystack[i]应与needle[matched]比较；相等就把这段匹配延长一位。若两者不同，已经匹配的部分就是
needle[0..matched-1]。要向右移动模式串并保留部分匹配，新模式串的前缀必须等于这段已匹配内容的后缀。定义lps[i]为needle[0..i]的最长相等真前后缀长度，其中“真”表示不能取整个字符串。因此，失配后的最长可用长度恰好是lps[matched-1]。回退后仍用同一个文本字符继续比较。如果还失配，就继续沿
lps回退：任何更短的可用长度，也必须是当前公共前后缀的公共前后缀，所以这条回退链不会漏掉候选。直到字符相等，或者退到0；若长度为0时仍不相等，这个文本字符便无法作为匹配的结尾。前缀表也按相同规则构造。
lps[0] = 0；计算lps[i]时，从matched = lps[i-1]对应的公共前后缀出发，用needle[i]尝试延长，失败就沿已算出的lps回退，最终把新长度记入lps[i]。从下标1开始，保证不会把整个前缀误当作真前后缀。文本扫描中，
matched首次达到模式串长度m时，匹配区间是i-m+1..i。文本结尾下标按递增顺序访问，而所有匹配长度相同，此时返回的起点就是第一次出现的位置。
解题步骤
- 代码先处理空模式串，返回
0；其余情况令模式串长度为m。- 从模式串下标
1开始构造lps。失配时反复执行matched = lps[matched-1]，相等时加一，再保存lps[i]。- 将
matched重置为0，从左到右扫描文本。- 当前字符失配时，只回退
matched，继续比较当前文本字符；若能匹配，就将matched加一。matched == m时立即返回i-m+1；扫描结束仍未完整匹配则返回-1。
代码实现
class Solution {
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) {
return 0;
}
int[] lps = buildLps(needle);
int matched = 0;
for (int i = 0; i < haystack.length(); i++) {
// 失配只回退已匹配长度，同一个文本字符还要继续尝试。
while (matched > 0 && haystack.charAt(i) != needle.charAt(matched)) {
matched = lps[matched - 1];
}
if (haystack.charAt(i) == needle.charAt(matched)) {
matched++;
}
if (matched == needle.length()) {
return i - needle.length() + 1;
}
}
return -1;
}
private int[] buildLps(String pattern) {
int[] lps = new int[pattern.length()];
int matched = 0;
for (int i = 1; i < pattern.length(); i++) {
// 构造前缀表也沿较短公共前后缀继续寻找可扩展位置。
while (matched > 0 && pattern.charAt(i) != pattern.charAt(matched)) {
matched = lps[matched - 1];
}
if (pattern.charAt(i) == pattern.charAt(matched)) {
matched++;
}
lps[i] = matched;
}
return lps;
}
}
func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
lps := buildLPS(needle)
matched := 0
for i := 0; i < len(haystack); i++ {
// 失配只回退已匹配长度，同一个文本字符还要继续尝试。
for matched > 0 && haystack[i] != needle[matched] {
matched = lps[matched-1]
}
if haystack[i] == needle[matched] {
matched++
}
if matched == len(needle) {
return i - len(needle) + 1
}
}
return -1
}
func buildLPS(pattern string) []int {
lps := make([]int, len(pattern))
matched := 0
for i := 1; i < len(pattern); i++ {
// 构造前缀表也沿较短公共前后缀继续寻找可扩展位置。
for matched > 0 && pattern[i] != pattern[matched] {
matched = lps[matched-1]
}
if pattern[i] == pattern[matched] {
matched++
}
lps[i] = matched
}
return lps
}
复杂度分析
设文本长度为
n，模式串长度为m。
- 时间复杂度：$O(n + m)$。构造表时下标前进 $m-1$ 次，匹配时前进 $n$ 次；每轮至多让
matched增加一，而每次回退都会使其减小，因此回退总次数不超过此前的增加次数，内层循环不会形成平方复杂度。- 空间复杂度：$O(m)$，用于保存前缀表。
关键点总结
[!green]
lps[i]是长度，不是下标；它描述模式串前缀0..i的最长相等真前后缀。- 失配后可复用的部分必须同时是已匹配串的后缀和模式串的前缀，回退到
lps[matched-1]正是最长候选。- 回退只改变模式串的匹配长度，当前文本字符仍要参与比较。
- 前缀表构造和文本匹配都遵循“失配回退、相等延长”；首次完整匹配即可返回。
易错点总结
[!yellow]
- 只回退一次而不用
while：新的候选位置也可能失配，必须继续缩短。- 写成
matched = lps[matched]：应查询已经匹配的最后一个位置matched-1，才能保证状态严格缩短。- 失配回退时同时前进文本下标，会跳过当前字符与较短模式前缀的匹配机会。
lps构造从下标0开始比较自己，会把整个前缀算进去；应保留lps[0] = 0，从1开始。- 返回值应为
i-m+1；代码在完整匹配后立即返回，不能继续访问needle[m]。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 459. 重复的子字符串 | 简单 | KMP前缀函数同样可复用，原题由最长边界判断字符串周期，本题定位模式首次出现。 |
| 686. 重复叠加字符串匹配 | 中等 | 原题允许重复源串直到包含模式，本题的匹配过程可作为重复后的查找子过程。 |
| 214. 最短回文串 | 困难 | 通过字符与模式前缀的匹配状态避免重复比较；本题寻找第一个完整匹配的位置，该题将回文前缀转为正反串匹配。 |
| 补充题 106. 字符串模式匹配计数 | 中等 | 都用 KMP 前缀表处理失配回退；补充题在每次匹配后继续回退以统计重叠出现。 |