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

Categories:

题目描述
思路分析
1. 解法一：KMP（推荐）
相似题目

题目描述

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

思路分析

解法一：KMP（推荐）

核心思路：

预处理模式串 needle 的最长相等前后缀数组 lps。

通过 lps 在失配时跳转，避免回退文本指针。

匹配成功时返回起始下标。

复杂度分析：

时间复杂度：O(n + m)，其中 n 表示 haystack 长度，m 表示 needle 长度。

空间复杂度：O(m)。

// KMP 字符串匹配
class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.isEmpty()) {
            return 0;
        }

        int[] lps = buildLps(needle);
        int i = 0;
        int j = 0;

        while (i < haystack.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                if (j == needle.length()) {
                    return i - j;
                }
            } else if (j > 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }

        return -1;
    }

    private int[] buildLps(String p) {
        int[] lps = new int[p.length()];
        int len = 0;
        for (int i = 1; i < p.length(); ) {
            if (p.charAt(i) == p.charAt(len)) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
}

// KMP 字符串匹配
func strStr(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}

	lps := buildLps(needle)
	i, j := 0, 0

	for i < len(haystack) {
		if haystack[i] == needle[j] {
			i++
			j++
			if j == len(needle) {
				return i - j
			}
		} else if j > 0 {
			j = lps[j-1]
		} else {
			i++
		}
	}

	return -1
}

func buildLps(p string) []int {
	lps := make([]int, len(p))
	length := 0
	for i := 1; i < len(p); {
		if p[i] == p[length] {
			length++
			lps[i] = length
			i++
		} else if length > 0 {
			length = lps[length-1]
		} else {
			lps[i] = 0
			i++
		}
	}
	return lps
}

相似题目

题目	难度	考察点
214. 最短回文串	困难	KMP
459. 重复的子字符串	简单	KMP
1392. 最长快乐前缀	困难	KMP
686. 重复叠加字符串匹配	中等	KMP
796. 旋转字符串	简单	KMP
438. 找到字符串中所有字母异位词	中等	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/73002846