Cover image for 面试经典150题 P28 找出字符串中第一个匹配项的下标

面试经典150题 P28 找出字符串中第一个匹配项的下标

Created:Updated:
algorithm
, , 
字数 638
阅读
访客
时间轴

时间轴

2025-10-06

init

KMP

题目：

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

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/?envType=study-plan-v2&envId=top-interview-150

实际上直接用 C++的 string.find 函数就能求值

1
2
3
4
5
6
7
#include <string>
using std::string;

class Solution {
public:
  int strStr(string haystack, string needle) { return haystack.find(needle); }
};

但是显然这题考察 KMP ：

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
class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        int i, j;

        if(m == 0) 
            return 0;

        vector<int> next(m, 0); // next[i] = p[0..i] 的最长相同前后缀长度

        // 构建 next 数组
        j = 0; // 当前最长前后缀长度
        for(i = 1; i < m; i++){ // 从1开始，因为至少要两个字符才能计算前后缀
            while(j > 0 && p[i] != p[j])
                j = next[j - 1]; // 退而求其次

            if(p[i] == p[j])
                j++;

            next[i] = j;
        }

        // 匹配
        j = 0; // 匹配字符串 p 的当前位置
        for(i = 0; i < n; i++){
            while(j > 0 && s[i] != p[j])
                j = next[j - 1];

            if(s[i] == p[j])
                j++;

            if(j == m)
                return i - m + 1;
        }

        return -1;
    }
};

求解 next 数组的例子

我们用最经典的模式串：

1
p = "ababaca"

下标：

1
2
index: 0 1 2 3 4 5 6
p    : a b a b a c a

我们要求next[i]：

1
next[i] = p[0..i] 的最长相同前后缀长度

前缀：从开头开始后缀：从结尾结束（但不能等于整个字符串）

初始化

1
2
next[0] = 0
j = 0

因为：“a” 没有前后缀

i = 1

1
2
p[1] = b
p[j] = p[0] = a

比较：b != a，因为j = 0，不能再回退。

1
next[1] = 0

当前：

1
next = [0,0]

i = 2

1
2
p[2] = a
p[j] = p[0] = a

匹配成功：

1
2
j++
j = 1

所以：

1
next[2] = 1

当前：

1
next = [0,0,1]

解释：

1
2
3
4
5
6
aba
前缀: a ab
后缀: a ba

最长相同 = a
长度 = 1

i = 3

1
2
p[3] = b
p[j] = p[1] = b

匹配：

1
2
3
j++
j = 2
next[3] = 2

当前：

1
next = [0,0,1,2]

解释：

1
2
3
4
5
abab
前缀: a ab aba
后缀: b ab bab

最长 = ab

i = 4

1
2
p[4] = a
p[j] = p[2] = a

匹配：

1
2
3
j++
j = 3
next[4] = 3

当前：

1
next = [0,0,1,2,3]

解释：

1
2
ababa
最长前后缀 = aba

i = 5（关键回退）

1
2
p[5] = c
p[j] = p[3] = b

不匹配：

1
c != b

开始回退：

1
2
3
j = next[j-1]
j = next[2]
j = 1

继续比较：

1
2
p[5] = c
p[1] = b

仍然不匹配：

1
2
3
j = next[j-1]
j = next[0]
j = 0

现在：j = 0 停止。

1
next[5] = 0

当前：

1
next = [0,0,1,2,3,0]

i = 6

1
2
p[6] = a
p[j] = p[0] = a

匹配：

1
2
3
j++
j = 1
next[6] = 1

最终结果

1
2
3
p = a b a b a c a
i = 0 1 2 3 4 5 6
next = 0 0 1 2 3 0 1