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

时间轴

2025-10-06

init

题目：

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 函数就能求值

#include <string>
using std::string;

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

但是显然这题考察 KMP ：

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]

解释：

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]

解释：

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

不匹配：

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