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

---

Timeline

Timeline

2025-10-06

init

KMP

---

Problem:

P28 Find the Index of the First Occurrence 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 the string.find function in C++ to compute it.

#include <string>
using std::string;

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

But obviously this problem tests 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] = the length of the longest common 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 compute the prefix and suffix
            while(j > 0 && p[i] != p[j])
                j = next[j - 1]; // Fall back to the next best

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

            next[i] = j;
        }

        // Match
        j = 0; // The current position in the pattern 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:

p = "ababaca"

Index:

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

We need to findnext[i]：

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

Prefix: starts from the beginning
Suffix: ends at the end (but cannot equal the entire string)

Initialize

next[0] = 0
j = 0

Because: “a” has no prefix and suffix

---

i = 1

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

Compare:b != a, becausej = 0, cannot fall back any further.

next[1] = 0

Current:

next = [0,0]

---

i = 2

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

Match successful:

j++
j = 1

So:

next[2] = 1

Current:

next = [0,0,1]

Explanation:

aba
前缀: a ab
后缀: a ba

最长相同 = a
长度 = 1

---

i = 3

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

Match:

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

Current:

next = [0,0,1,2]

Explanation:

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

最长 = ab

---

i = 4

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

Match:

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

Current:

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

Explanation:

ababa
最长前后缀 = aba

---

i = 5 (key backtrack)

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

Mismatch:

c != b

Start backtracking:

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

Continue comparing:

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

Still mismatch:

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

Now: j = 0 Stop.

next[5] = 0

Current:

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

---

i = 6

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

Match:

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

---

Final result

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