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

---

时间轴

时间轴

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

#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 数组的例子

我们用最经典的模式串：

p = "ababaca"

下标：

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

我们要求next[i]：

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

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

初始化

next[0] = 0
j = 0

因为：“a” 没有前后缀

---

i = 1

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

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

next[1] = 0

当前：

next = [0,0]

---

i = 2

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

匹配成功：

j++
j = 1

所以：

next[2] = 1

当前：

next = [0,0,1]

解释：

aba
前缀: a ab
后缀: a ba

最长相同 = a
长度 = 1

---

i = 3

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

匹配：

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

当前：

next = [0,0,1,2]

解释：

abab
前缀: a ab aba
后缀: b ab bab

最长 = ab

---

i = 4

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

匹配：

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

当前：

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

解释：

ababa
最长前后缀 = aba

---

i = 5（关键回退）

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

不匹配：

c != b

开始回退：

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

继续比较：

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

仍然不匹配：

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

现在：j = 0 停止。

next[5] = 0

当前：

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

---

i = 6

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

匹配：

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

---

最终结果

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