Cover image for Interview Classic 150 Questions P28 Find the Index of the First Match in a String

Interview Classic 150 Questions P28 Find the Index of the First Match in a String

(Updated: )
algorithm
, ,
Timeline

Timeline

2025-10-06

init

KMP

Title:

P28 Find the Index of the First Match in a String

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

Actually, you can directly use C++'s string.find function to get the value

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); }
};

But obviously this question tests 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] = the length of the longest equal prefix and suffix of p[0..i]

        // Build the next array
        j = 0; // Current longest prefix-suffix length
        for(i = 1; i < m; i++){ // Start from 1, because at least two characters are needed to calculate prefix and suffix
            while(j > 0 && p[i] != p[j])
                j = next[j - 1]; // Settle for the next best

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

            next[i] = j;
        }

        // Match
        j = 0; // Current position matching string 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;
    }
};

Example of solving the next array

We use the most classic pattern string:

1
p = "ababaca"

Index:

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

We requirenext[i]：

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

Prefix: starting from the beginning
Suffix: ending at the end (but cannot equal the entire string)

Initialization

1
2
next[0] = 0
j = 0

Because: “a” has no prefix or suffix

i = 1

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

Comparison:b != a, becausej = 0, cannot backtrack further.

1
next[1] = 0

Current:

1
next = [0,0]

i = 2

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

Match successful:

1
2
j++
j = 1

Therefore:

1
next[2] = 1

Current:

1
next = [0,0,1]

Explanation:

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

Match:

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

Current:

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

Explanation:

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

Match:

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

Current:

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

Explanation:

1
2
ababa
最长前后缀 = aba

i = 5 (critical backtrack)

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

Mismatch:

1
c != b

Start backtrack:

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

Continue comparison:

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

Still mismatch:

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

Now: j = 0. Stop.

1
next[5] = 0

Current:

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

i = 6

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

Match:

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

Final result

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