LeetCode 28: Find the Index of the First Occurrence in a String (KMP Prefix Function)
LeetCode 28StringKMPInterviewToday we solve LeetCode 28 - Find the Index of the First Occurrence in a String.
Source: https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/
English
Problem Summary
Given strings haystack and needle, return the first index where needle appears in haystack, or -1 if it does not appear.
Key Insight
KMP avoids re-checking characters in haystack by precomputing a prefix table (lps) for needle. On mismatch, we jump the pattern pointer to the longest valid prefix length instead of restarting from zero.
Brute Force and Limitations
Brute force compares needle from every start position in haystack, worst-case O(nm). For repetitive text like aaaa...ab, this becomes inefficient.
Optimal Algorithm Steps
1) Build lps array for needle where lps[i] is the longest proper prefix that is also suffix for needle[0..i].
2) Scan haystack with index i, pattern index j.
3) If chars match: increment both indices.
4) If mismatch and j > 0: set j = lps[j - 1].
5) If mismatch and j == 0: increment i.
6) When j == needle.length, return i - j.
Complexity Analysis
Time: O(n + m).
Space: O(m) for lps.
Common Pitfalls
- Building lps incorrectly when fallback is needed multiple times.
- Returning wrong index (must be i - j after full match).
- Forgetting edge case: empty needle should return 0.
- Resetting j to 0 on every mismatch and losing KMP advantage.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int[] lps = buildLps(needle);
int i = 0, j = 0;
while (i < haystack.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
if (j == needle.length()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
private int[] buildLps(String p) {
int[] lps = new int[p.length()];
int len = 0;
int i = 1;
while (i < p.length()) {
if (p.charAt(i) == p.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
}func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
lps := buildLps(needle)
i, j := 0, 0
for i < len(haystack) {
if haystack[i] == needle[j] {
i++
j++
if j == len(needle) {
return i - j
}
} else if j > 0 {
j = lps[j-1]
} else {
i++
}
}
return -1
}
func buildLps(p string) []int {
lps := make([]int, len(p))
length := 0
i := 1
for i < len(p) {
if p[i] == p[length] {
length++
lps[i] = length
i++
} else if length > 0 {
length = lps[length-1]
} else {
lps[i] = 0
i++
}
}
return lps
}class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
vector<int> lps = buildLps(needle);
int i = 0, j = 0;
while (i < (int)haystack.size()) {
if (haystack[i] == needle[j]) {
i++;
j++;
if (j == (int)needle.size()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
private:
vector<int> buildLps(const string& p) {
vector<int> lps(p.size(), 0);
int len = 0;
int i = 1;
while (i < (int)p.size()) {
if (p[i] == p[len]) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
};class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
lps = self.build_lps(needle)
i = j = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif j > 0:
j = lps[j - 1]
else:
i += 1
return -1
def build_lps(self, p: str) -> list[int]:
lps = [0] * len(p)
length = 0
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lpsvar strStr = function(haystack, needle) {
if (needle.length === 0) return 0;
const lps = buildLps(needle);
let i = 0;
let j = 0;
while (i < haystack.length) {
if (haystack[i] === needle[j]) {
i++;
j++;
if (j === needle.length) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
};
function buildLps(p) {
const lps = new Array(p.length).fill(0);
let len = 0;
let i = 1;
while (i < p.length) {
if (p[i] === p[len]) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}中文
题目概述
给定字符串 haystack 和 needle，返回 needle 在 haystack 中首次出现的位置；如果不存在则返回 -1。
核心思路
使用 KMP。先为 needle 预处理 lps（最长相等前后缀）数组，匹配失败时直接让模式串指针跳到可复用位置，避免主串回退。
暴力解法与不足
暴力做法是主串每个起点都尝试匹配一次，最坏为 O(nm)。当字符串重复度高时会产生大量重复比较。
最优算法步骤
1）构建 needle 的 lps 数组。
2）双指针扫描：i 指向 haystack，j 指向 needle。
3）字符相等时同时前进。
4）失配且 j > 0 时，令 j = lps[j - 1]。
5）失配且 j == 0 时，i 前进。
6）当 j == needle.length 时，答案是 i - j。
复杂度分析
时间复杂度：O(n + m)。
空间复杂度：O(m)。
常见陷阱
- lps 构建时忘记连续回退，导致表错误。
- 匹配完成返回下标写错（应返回 i - j）。
- 忽略空模式串，按题意应返回 0。
- 失配时直接把 j 清零，失去 KMP 的线性优势。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int strStr(String haystack, String needle) {
if (needle.isEmpty()) return 0;
int[] lps = buildLps(needle);
int i = 0, j = 0;
while (i < haystack.length()) {
if (haystack.charAt(i) == needle.charAt(j)) {
i++;
j++;
if (j == needle.length()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
private int[] buildLps(String p) {
int[] lps = new int[p.length()];
int len = 0;
int i = 1;
while (i < p.length()) {
if (p.charAt(i) == p.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
}func strStr(haystack string, needle string) int {
if len(needle) == 0 {
return 0
}
lps := buildLps(needle)
i, j := 0, 0
for i < len(haystack) {
if haystack[i] == needle[j] {
i++
j++
if j == len(needle) {
return i - j
}
} else if j > 0 {
j = lps[j-1]
} else {
i++
}
}
return -1
}
func buildLps(p string) []int {
lps := make([]int, len(p))
length := 0
i := 1
for i < len(p) {
if p[i] == p[length] {
length++
lps[i] = length
i++
} else if length > 0 {
length = lps[length-1]
} else {
lps[i] = 0
i++
}
}
return lps
}class Solution {
public:
int strStr(string haystack, string needle) {
if (needle.empty()) return 0;
vector<int> lps = buildLps(needle);
int i = 0, j = 0;
while (i < (int)haystack.size()) {
if (haystack[i] == needle[j]) {
i++;
j++;
if (j == (int)needle.size()) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
}
private:
vector<int> buildLps(const string& p) {
vector<int> lps(p.size(), 0);
int len = 0;
int i = 1;
while (i < (int)p.size()) {
if (p[i] == p[len]) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
};class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle:
return 0
lps = self.build_lps(needle)
i = j = 0
while i < len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1
if j == len(needle):
return i - j
elif j > 0:
j = lps[j - 1]
else:
i += 1
return -1
def build_lps(self, p: str) -> list[int]:
lps = [0] * len(p)
length = 0
i = 1
while i < len(p):
if p[i] == p[length]:
length += 1
lps[i] = length
i += 1
elif length > 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
return lpsvar strStr = function(haystack, needle) {
if (needle.length === 0) return 0;
const lps = buildLps(needle);
let i = 0;
let j = 0;
while (i < haystack.length) {
if (haystack[i] === needle[j]) {
i++;
j++;
if (j === needle.length) return i - j;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
}
return -1;
};
function buildLps(p) {
const lps = new Array(p.length).fill(0);
let len = 0;
let i = 1;
while (i < p.length) {
if (p[i] === p[len]) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
lps[i++] = 0;
}
}
return lps;
}
Comments