LeetCode 28. 找出字符串中第一个匹配项的下标

2024-07-17 HGNULB 约 6 分钟

文章信息 13 个分类 6 个标签

分类

LeetCode CodeTop 简单未解决 10-20 字节跳动微软美团腾讯百度亚马逊携程面试经典 150 题

题目描述

✅ 28. 找出字符串中第一个匹配项的下标

题意分析

给定主串 haystack 和模式串 needle，返回 needle 在 haystack 中第一次出现的起始下标；如果不存在，返回 -1。

题目本身的定义没有歧义，需要留意的是两个词：一是「第一次」，找到就可以立刻返回，不需要统计全部出现位置；二是返回的是起始下标，而匹配是在末尾字符处宣告成功的，两者之间差一个模式串长度，这是最常见的低级错误来源。

数据范围是 $1 \le n, m \le 10^4$，两个串都只含小写英文字母。这个规模其实朴素匹配的 $O(nm)$ 也能过，题目也被标成简单题。但它在面试中的地位完全不同：这道题就是字符串匹配算法的载体，面试官出它的目的是听你讲清楚如何做到线性时间，直接调库函数等于放弃作答。

需要照顾的边界包括：模式串比主串长时必然返回 -1；模式串恰好等于主串时返回 0；主串里有多处匹配时只返回最左边的那个；主串中存在大量部分匹配（比如 "aaaaab" 里找 "aaab"）时算法不能退化。

解法：KMP 前缀表匹配

核心思路

暴力匹配在失配后把起点右移一位，会重复比较已经确认过的字符。KMP 的关键是：利用模式串自身的前后缀关系，决定失配后还能保留多少匹配结果，文本指针始终不回退。

定义 lps[i] 为 needle[0..i] 的最长相等真前缀与后缀长度。匹配时用 matched 表示当前已经匹配的模式串前缀长度。若文本字符与 needle[matched] 不同，就令：

matched = lps[matched - 1]

这相当于把已匹配片段的最长公共前后缀对齐到当前位置。若仍不匹配就继续回退；匹配则把 matched 加一。首次达到模式串长度时，当前匹配的起点就是 i - m + 1。

不变量是：处理完 haystack[i] 后，matched 始终等于“文本已处理前缀的后缀”与“模式串前缀”能匹配的最大长度。因此跳转只丢弃已经证明不可能的候选起点，不会漏解。

解题步骤

模式串为空时返回 0。

构造 lps：匹配时扩展公共前后缀，失配时沿已有 lps 连续回退。

扫描文本；失配时只回退 matched，不移动文本下标。

当前字符匹配后令 matched++；若等于模式串长度，立即返回起点。

扫描结束仍未完整匹配则返回 -1。

例如模式串 "ababaca" 的 lps 为 [0,0,1,2,3,0,1]。在已匹配 "ababa" 后失配，可以直接把有效匹配长度从 5 回退到 3，无需重新比较文本中的整段字符。

代码实现

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)$。构造前缀表是 $O(m)$；匹配时 matched 的增加与回退次数都受线性范围约束。

空间复杂度：$O(m)$，用于保存模式串的前缀表。

关键点总结

lps[i] 表示长度，不是下标；失配时回退到 lps[matched - 1]。

KMP 复用的是模式串的最长公共前后缀，因此文本下标不需要回退。

构造前缀表和匹配文本使用的是同一套“失配回退、相等扩展”逻辑。

找到完整匹配时立即返回，天然得到第一次出现的位置。

易错点总结

失配时只回退一次而不用 while，可能回退后仍不匹配。

写成 matched = lps[matched] 会越界或无法缩短状态，正确位置是 matched - 1。

把 lps 当作匹配起点下标，会导致返回位置偏移。

忘记处理空模式串，会在访问 needle[0] 时越界。

Go 代码按字节匹配；本题字符集为英文字母，若扩展到 Unicode 文本应先转换为 []rune。

相似题目

题目	难度	考察点
214. 最短回文串	困难	用前缀表求最长回文前缀
459. 重复的子字符串	简单	用 `lps` 末位判断串的周期
796. 旋转字符串	简单	在自拼接串上做子串查找
1408. 数组中的字符串匹配	简单	多个串之间的两两包含判定
面试题 01.09. 字符串轮转	简单	一次子串查询判断是否为轮转