LeetCode 28. 找出字符串中第一个匹配项的下标（暴力匹配 + KMP 算法详解）

ZCH��

236人浏览 · 2026-08-20 21:29:57

ZCH�� · 2026-08-20 21:29:57 发布

LeetCode 28. 找出字符串中第一个匹配项的下标（暴力匹配 + KMP 算法详解）

题目链接

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

题目描述

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

示例

示例 1

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0，所以返回 0。

示例 2

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1。

提示

1 <= haystack.length, needle.length <= 10^4
haystack 和 needle 仅由小写英文字符组成

解题思路

这道题是字符串匹配的经典问题，主要有两种解法：

暴力匹配：简单直观，时间复杂度 O(m×n)。
KMP 算法：高效，时间复杂度 O(m+n)。

方法一：暴力匹配

思路

从主串 haystack 的每个位置开始，尝试与模式串 needle 进行匹配：

遍历主串的每个可能的起点 i（从 0 到 m-n）。
对于每个起点，逐个字符比较 haystack[i+j] 和 needle[j]。
如果所有字符都匹配（j == n），返回起点 i。
如果没有任何起点匹配成功，返回 -1。

Python 代码

def strStr_brute(haystack: str, needle: str) -> int:
    m = len(haystack)
    n = len(needle)
    # i主串起点
    for i in range(m - n + 1):
        j = 0
        while j < n and haystack[i + j] == needle[j]:
            j += 1
        if j == n:
            return i
    return -1

Java 代码

class BruteForce {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            while (j < n && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == n) {
                return i;
            }
        }
        return -1;
    }
}

复杂度分析

时间复杂度：O(m×n)，其中 m 是主串长度，n 是模式串长度。最坏情况下需要比较 m×n 次。
空间复杂度：O(1)。

优缺点

优点：简单直观，易于理解。
缺点：时间复杂度高，在字符串较长时可能超时。

方法二：KMP 算法

思路

KMP（Knuth-Morris-Pratt）算法的核心思想是：利用已经匹配过的信息，避免重复匹配。

当匹配失败时，不是简单地将模式串向后移动一位，而是根据 前缀函数（next 数组） 跳过不可能匹配的位置。

什么是 next 数组？

next[i] 表示模式串 needle[0...i] 中，最长的相同前缀和后缀的长度。

例如，模式串 "ababc" 的 next 数组为 [0, 0, 1, 2, 0]：

next[0] = 0：单个字符没有前缀和后缀。
next[1] = 0："ab" 没有相同的前缀和后缀。
next[2] = 1："aba" 的前缀 "a" 和后缀 "a" 相同。
next[3] = 2："abab" 的前缀 "ab" 和后缀 "ab" 相同。
next[4] = 0："ababc" 没有相同的前缀和后缀。

KMP 匹配过程

使用两个指针 i（主串）和 j（模式串）。
当 haystack[i] == needle[j] 时，两个指针都向后移动。
当不匹配时：
- 如果 j > 0，将 j 回退到 next[j-1]，继续匹配。
- 如果 j == 0，将 i 向后移动。
当 j == n 时，说明匹配成功，返回 i - j。

Python 代码

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def build_next(pattern):
            n = len(pattern)
            next_arr = [0] * n
            prefix_len = 0
            i = 1
            while i < n:
                if pattern[prefix_len] == pattern[i]:
                    prefix_len += 1
                    next_arr[i] = prefix_len
                    i += 1
                else:
                    if prefix_len == 0:
                        next_arr[i] = 0
                        i += 1
                    else:
                        prefix_len = next_arr[prefix_len - 1]
            return next_arr

        next_arr = build_next(needle)
        i = 0  # haystack
        j = 0  # needle
        while i < len(haystack):
            if haystack[i] == needle[j]:
                i += 1
                j += 1
            elif j > 0:
                j = next_arr[j - 1]
            else:
                i += 1
            if j == len(needle):
                return i - j
        return -1

Java 代码

class KMP {
    public int strStr(String haystack, String needle) {
        int[] next = buildNext(needle);
        int i = 0; // haystack指针
        int j = 0; // needle指针
        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
            if (j == needle.length()) {
                return i - j;
            }
        }
        return -1;
    }

    private int[] buildNext(String needle) {
        int n = needle.length();
        int[] next = new int[n];
        int prefixLen = 0;
        int i = 1;
        while (i < n) {
            if (needle.charAt(prefixLen) == needle.charAt(i)) {
                prefixLen++;
                next[i] = prefixLen;
                i++;
            } else {
                if (prefixLen == 0) {
                    next[i] = 0;
                    i++;
                } else {
                    prefixLen = next[prefixLen - 1];
                }
            }
        }
        return next;
    }
}

复杂度分析

时间复杂度：O(m+n)，其中 m 是主串长度，n 是模式串长度。构建 next 数组需要 O(n)，匹配过程需要 O(m)。
空间复杂度：O(n)，需要存储 next 数组。

优点

时间复杂度低，适合处理长字符串。
是字符串匹配的经典算法，面试常考。

KMP 算法详解

构建 next 数组

def build_next(pattern):
    n = len(pattern)
    next_arr = [0] * n
    prefix_len = 0
    i = 1
    while i < n:
        if pattern[prefix_len] == pattern[i]:
            prefix_len += 1
            next_arr[i] = prefix_len
            i += 1
        else:
            if prefix_len == 0:
                next_arr[i] = 0
                i += 1
            else:
                prefix_len = next_arr[prefix_len - 1]
    return next_arr

关键点：

prefix_len 表示当前最长相同前缀后缀的长度。
当 pattern[prefix_len] == pattern[i] 时，说明可以扩展最长相同前缀后缀。
当不匹配时，回退 prefix_len 到 next_arr[prefix_len - 1]，继续尝试。

匹配过程

i = 0  # haystack
j = 0  # needle
while i < len(haystack):
    if haystack[i] == needle[j]:
        i += 1
        j += 1
    elif j > 0:
        j = next_arr[j - 1]
    else:
        i += 1
    if j == len(needle):
        return i - j