Find the Index of the First Occurrence in a String

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

分析

解题思路：KMP 算法

为了高效地查找子串，KMP 算法（Knuth-Morris-Pratt）通过构建部分匹配表 next 数组，在匹配失败时跳过不必要的字符比较，避免重复匹配

构建部分匹配表（next数组）
- 含义：next[i] 表示 needle[0...i] 的最长相等前后缀长度
- 作用：当匹配失败时，needle 可以直接跳到合适的位置，减少比较次数
构建过程：
- 用两个指针：i 遍历 needle，j 记录当前最长前后缀长度
- 如果 needle[i] == needle[j]，则 j++，更新 next[i] = j
- 如果不相等，回溯 j = next[j - 1]
主串匹配
- 用两个指针：i 遍历 haystack，j 遍历 needle
- 如果字符相等，i ++，j ++
- 如果不相等，则 j 回溯到 next[j - 1]
- 当 j == needle.size()，表示完全匹配，返回起始下标 i - m + 1

时间复杂度

构建 next 数组：O(m)
主串匹配：O(n)

总时间复杂度 O(n + m)

空间复杂度

空间复杂度为 O(m)

C++代码

 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


class Solution
{
public:
    int strStr(string haystack, string needle)
    {
        int n = haystack.size(), m = needle.size();
        if (m == 0)  // 特殊情况：needle为空，返回0
            return 0;

        // 构建next数组
        std::vector<int> next(m);
        for (int i = 1, j = 0; i < m; ++i)
        {
            while (j > 0 && needle[i] != needle[j])  // 回退
                j = next[j - 1];
            if (needle[i] == needle[j])  // 匹配成功
                ++j;
            next[i] = j;  // 更新next数组
        }

        // 匹配过程
        for (int i = 0, j = 0; i < n; ++i)
        {
            while (j > 0 && haystack[i] != needle[j])  // 回退
                j = next[j - 1];
            if (haystack[i] == needle[j])  // 匹配成功
                ++j;
            if (j == m)  // 完全匹配
                return i - m + 1;
        }

        return -1;  // 匹配失败
    }
};