实现strStr()

发表于 更新于 分类于

算法-实现strStr()

背景

  • 算法–实现strStr()

  • 博主以代码随想录算法公开课进行学习

题目

  • 实现 strStr() 函数。

    给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

    示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2

    示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

    说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

思路

  • strStr () 的本质是「字符串匹配」：在haystack（主串）中找needle（模式串）的第一个出现位置。
  • 前缀表（next 数组）：记录模式串needle中每个位置的「最长相等前后缀长度」，目的是当匹配失败时，模式串不用从头匹配，而是回退到最长相等前缀的位置，减少重复匹配。
    • 前缀：不包含最后一个字符的所有以第一个字符开头的子串（比如"abc"的前缀是"a"、"ab"）；
    • 后缀：不包含第一个字符的所有以最后一个字符结尾的子串（比如"abc"的后缀是"c"、"bc"）；
  • 匹配过程：
    • 用两个指针i（主串指针）、j（模式串指针）遍历；
    • 当haystack[i] == needle[j]时，两个指针同时后移；
    • 当匹配失败时，j根据 next 数组回退（j = next[j-1]），而i不回退；
    • 当j == needle.length()时，说明匹配成功，返回起始位置i - needle.length() + 1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
    public int strStr(String haystack, String needle) {
        // 1. 处理边界：模式串为空，直接返回0（题目要求）
        if(needle.length() == 0){
            return 0;
        }
         // 2. 构建next数组（前缀表），长度等于模式串长度
        int[] next = new int[needle.length()];
        getNext(next,needle);
        
        int j = 0;// 模式串指针，初始为0
         // 3. 遍历主串（i是主串指针）
        for(int i = 0;i < haystack.length();i++){
         // 3.1 匹配失败：j回退（直到j=0或匹配成功）
            while(j > 0 && needle.charAt(j) != haystack.charAt(i)){
                j = next[j-1];// 核心：根据前缀表回退，避免暴力回退
            }
            // 3.2 匹配成功：j后移
            if(needle.charAt(j) ==  haystack.charAt(i)){
                j++;
            }
             // 3.3 完全匹配：返回起始位置
            if(j == needle.length()){
                return i - needle.length() + 1;
            }
        }
        return -1;
        
    }
    // 构建next数组（前缀表）的核心方法
    private void getNext(int[] next,String needle){
        int j = 0;// j表示最长相等前后缀的长度，也指向前缀的末尾
        next[0] = 0;
        for(int i = 1; i < needle.length(); i++){
             // 前后缀不相等时，j回退到上一个前缀表的位置，直到相等或j=0
            while(j > 0&&needle.charAt(j) != needle.charAt(i)){
                j = next[j - 1];
            }
           // 前后缀相等，j后移（最长相等前后缀长度+1）
            if(needle.charAt(j) == needle.charAt(i)){
                j++;
            }
             // 记录当前位置的前缀表值
            next[i] = j;
        }
    }
}

总结

  • KMP 算法的核心价值
    • 解决「字符串匹配」问题，避免暴力匹配的重复遍历，时间复杂度从 O (n*m) 优化到 O (n+m)；
    • 前缀表（next 数组）是 KMP 的灵魂，作用是「记录模式串每个位置的最长相等前后缀长度，匹配失败时指导模式串指针回退」。