LeetCode 补拙笔记

0. 前言

• 日期：2026.05.28
• 题目：28. 找出字符串中第一个匹配项的下标
• 难度：简单
• 标签：字符串、KMP、双指针

1. 题目理解

问题描述： 给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1。

示例：

输入：haystack = "sadbutsad", needle = "sad" 输出：0

输入：haystack = "leetcode", needle = "leeto" 输出：-1

2. 解题思路

核心观察

• 本题是经典的字符串模式匹配问题。
• 暴力解法：枚举所有起点，逐位比较，简单直观但效率一般。
• KMP 解法：利用前缀函数跳过无效比较，效率更高。

算法步骤

1. 枚举原串的起始位置。
2. 逐位比较原串和模式串。
3. 完全匹配则返回起点，否则继续。
4. 遍历结束无匹配返回 -1。

3. 代码实现

package lc0_lc99.lc28;

class Solution {

    public static int[] next(String s2) {
        int[] next = new int[s2.length()];
        next[0] = 0;
        for (int i = 1; i < s2.length(); i++) {
            int len = next[i - 1];

            while (len != 0 && s2.charAt(i) != s2.charAt(len)) {
                len = next[len - 1];
            }
            if (s2.charAt(i) == s2.charAt(len)) {
                len++;
            }
            next[i] = len;
        }
        return next;
    }

    public static int kmp(String s1, String s2) {
        int[] next = next(s2);
        int len = 0;
        for (int i = 0; i < s1.length(); i++) {
            char a = s1.charAt(i);
            char b = s2.charAt(len);

            while (len != 0 && a != b) {
                len = next[len - 1];
                b = s2.charAt(len);
            }
            if (a == b) {
                len++;
                if (len == s2.length()) {
                    return i - s2.length() - 1;
                }
            }

        }
        return -1;
    }

    public int strStr(String haystack, String needle) {

        return kmp(haystack, needle);

    }
}

4. 代码优化说明

（代码未做任何修改，仅添加注释讲解）

class Solution {
public int strStr(String ss, String pp) {
    // 获取两个字符串长度
    int n = ss.length(), m = pp.length();
    // 转字符数组，访问更快
    char[] s = ss.toCharArray(), p = pp.toCharArray();
    
    // 枚举原串的所有可能起点
    for (int i = 0; i <= n - m; i++) {
        // a：原串指针  b：模式串指针
        int a = i, b = 0;
        // 逐位匹配
        while (b < m && s[a] == p[b]) {
            a++;
            b++;
        }
        // 模式串匹配完成，返回起点
        if (b == m) return i;
    }
    // 无匹配
    return -1;
}
}

5. 复杂度分析

• 暴力解法
  • 时间复杂度：$O(n\times m)$
  • 空间复杂度：$O(1)$
• KMP 解法
  • 时间复杂度：$O(n+m)$
  • 空间复杂度：$O(m)$

6. 总结

• 暴力法：代码极简、无额外空间，适合短字符串。
• KMP 法：线性复杂度，适合大数据场景。
• 本题核心：字符串模式匹配，两种解法都是面试必背模板。