28. 找出字符串中第一个匹配项的下标
题目描述
输入两个字符串 haystack 和 needle。
在 haystack 中查找 needle 作为连续子串出现的位置，返回最早一次出现的起始下标，下标从 0 开始。
如果 needle 从未在 haystack 中出现，返回 -1。
示例 1
输入：haystack = "sadbutsad", needle = "sad" 输出：0
解释："sad" 在下标 0 和 6 都出现过，最早的是 0。
示例 2
输入：haystack = "leetcode", needle = "leeto" 输出：-1
解释："leetcode" 中找不到 "leeto"。
数据范围
1 <= haystack.length, needle.length <= 10^4- 两个字符串都只含小写英文字母。
解题思路：暴力匹配
用两个指针：i 是尝试的起点，j 是 needle 中正在比对的位置。对每个起点 i，j 从 0 往右逐个比较 haystack[i + j] 与 needle[j]，相同就继续；遇到不同就换下一个起点。j 走到 m 说明整个 needle 都对上了，返回 i。起点只需试到 n − m，再往后剩余长度不够。
为什么正确
处理起点 i 时，所有更小的起点都已确认不匹配；内层循环中 haystack[i : i + j] == needle[:j]。
复杂度分析
最坏时间 O((n − m + 1) · m)，如 haystack="aaaa…ab"、needle="aab"；空间 O(1)。KMP 可以做到 O(n + m)。
易错点
外层循环上界是 n − m（含），写成 n − m 不含会漏掉 needle 在末尾的情况，不加限制则 haystack[i + j] 会越界。needle 比 haystack 长时循环一次也不执行，直接返回 -1。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
j = 0
while j < m and haystack[i + j] == needle[j]:
j += 1
if j == m:
return i
return -1class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && haystack.charAt(i + j) == needle.charAt(j)) {
j++;
}
if (j == m) {
return i;
}
}
return -1;
}
}class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
for (int i = 0; i + m <= n; i++) {
int j = 0;
while (j < m && haystack[i + j] == needle[j]) {
j++;
}
if (j == m) {
return i;
}
}
return -1;
}
};func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
for i := 0; i+m <= n; i++ {
j := 0
for j < m && haystack[i+j] == needle[j] {
j++
}
if j == m {
return i
}
}
return -1
}var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
for (let i = 0; i + m <= n; i++) {
let j = 0;
while (j < m && haystack[i + j] === needle[j]) {
j++;
}
if (j === m) {
return i;
}
}
return -1;
};function strStr(haystack: string, needle: string): number {
const n = haystack.length, m = needle.length;
for (let i = 0; i + m <= n; i++) {
let j = 0;
while (j < m && haystack[i + j] === needle[j]) {
j++;
}
if (j === m) {
return i;
}
}
return -1;
}其他解法
暴力匹配最简单但最坏 O(n·m)；KMP 用前缀函数保证最坏线性；Rabin-Karp 用滚动哈希在期望线性时间内筛掉不可能的位置。
解法 2：KMP 算法 时间 O(n+m)，空间 O(m)
先为 needle 求前缀函数 pi：pi[i] 是 needle[0..i] 最长的相等真前缀与真后缀的长度。再扫描 haystack，j 表示当前已匹配的长度；字符不等时把 j 回退到 pi[j-1]，而不是把 haystack 的指针退回去。j 达到 m 时返回 i-m+1。
haystack 的指针从不后退，最坏情况也是线性时间。前缀函数的含义和回退过程较难理解，短串上未必比暴力快。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
if m == 0:
return 0
pi = [0] * m
j = 0
for i in range(1, m):
while j > 0 and needle[i] != needle[j]:
j = pi[j - 1]
if needle[i] == needle[j]:
j += 1
pi[i] = j
j = 0
for i in range(n):
while j > 0 and haystack[i] != needle[j]:
j = pi[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == m:
return i - m + 1
return -1class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m == 0) return 0;
int[] pi = new int[m];
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle.charAt(i) != needle.charAt(j)) j = pi[j - 1];
if (needle.charAt(i) == needle.charAt(j)) j++;
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack.charAt(i) != needle.charAt(j)) j = pi[j - 1];
if (haystack.charAt(i) == needle.charAt(j)) j++;
if (j == m) return i - m + 1;
}
return -1;
}
}class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m == 0) return 0;
vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] != needle[j]) j = pi[j - 1];
if (needle[i] == needle[j]) j++;
pi[i] = j;
}
for (int i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] != needle[j]) j = pi[j - 1];
if (haystack[i] == needle[j]) j++;
if (j == m) return i - m + 1;
}
return -1;
}
};func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
if m == 0 {
return 0
}
pi := make([]int, m)
for i, j := 1, 0; i < m; i++ {
for j > 0 && needle[i] != needle[j] {
j = pi[j-1]
}
if needle[i] == needle[j] {
j++
}
pi[i] = j
}
for i, j := 0, 0; i < n; i++ {
for j > 0 && haystack[i] != needle[j] {
j = pi[j-1]
}
if haystack[i] == needle[j] {
j++
}
if j == m {
return i - m + 1
}
}
return -1
}var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
if (m === 0) return 0;
const pi = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) j = pi[j - 1];
if (needle[i] === needle[j]) j++;
pi[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] !== needle[j]) j = pi[j - 1];
if (haystack[i] === needle[j]) j++;
if (j === m) return i - m + 1;
}
return -1;
};function strStr(haystack: string, needle: string): number {
const n = haystack.length, m = needle.length;
if (m === 0) return 0;
const pi: number[] = new Array(m).fill(0);
for (let i = 1, j = 0; i < m; i++) {
while (j > 0 && needle[i] !== needle[j]) j = pi[j - 1];
if (needle[i] === needle[j]) j++;
pi[i] = j;
}
for (let i = 0, j = 0; i < n; i++) {
while (j > 0 && haystack[i] !== needle[j]) j = pi[j - 1];
if (haystack[i] === needle[j]) j++;
if (j === m) return i - m + 1;
}
return -1;
}解法 3：Rabin-Karp 滚动哈希 时间 O(n+m)，空间 O(1)
把长度为 m 的字符串看成 B 进制数，对大质数取模得到哈希值。窗口右移一位时，减去最高位字符乘 B^(m-1) 的贡献，再乘 B 并加上新字符，O(1) 得到新哈希。哈希值与 needle 相等时，再逐字符比较一次以排除冲突。
思路直观，并且能推广到多模式串和二维匹配。期望复杂度是线性的，但哈希冲突很多时会退化到 O(n·m)；还要小心取模运算的溢出。
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
n, m = len(haystack), len(needle)
if m > n:
return -1
B, MOD = 131, 1_000_000_007
pw = 1
for _ in range(m - 1):
pw = pw * B % MOD
hn = hh = 0
for i in range(m):
hn = (hn * B + ord(needle[i])) % MOD
hh = (hh * B + ord(haystack[i])) % MOD
for i in range(n - m + 1):
if hh == hn and haystack[i:i + m] == needle:
return i
if i + m < n:
hh = (hh - ord(haystack[i]) * pw % MOD + MOD) % MOD
hh = (hh * B + ord(haystack[i + m])) % MOD
return -1class Solution {
public int strStr(String haystack, String needle) {
int n = haystack.length(), m = needle.length();
if (m > n) return -1;
final long B = 131, MOD = 1000000007L;
long pw = 1;
for (int i = 0; i < m - 1; i++) pw = pw * B % MOD;
long hn = 0, hh = 0;
for (int i = 0; i < m; i++) {
hn = (hn * B + needle.charAt(i)) % MOD;
hh = (hh * B + haystack.charAt(i)) % MOD;
}
for (int i = 0; i + m <= n; i++) {
if (hh == hn && haystack.startsWith(needle, i)) return i;
if (i + m < n) {
hh = (hh - haystack.charAt(i) * pw % MOD + MOD) % MOD;
hh = (hh * B + haystack.charAt(i + m)) % MOD;
}
}
return -1;
}
}class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
if (m > n) return -1;
const long long B = 131, MOD = 1000000007;
long long pw = 1;
for (int i = 0; i < m - 1; i++) pw = pw * B % MOD;
long long hn = 0, hh = 0;
for (int i = 0; i < m; i++) {
hn = (hn * B + needle[i]) % MOD;
hh = (hh * B + haystack[i]) % MOD;
}
for (int i = 0; i + m <= n; i++) {
if (hh == hn && haystack.compare(i, m, needle) == 0) return i;
if (i + m < n) {
hh = (hh - haystack[i] * pw % MOD + MOD) % MOD;
hh = (hh * B + haystack[i + m]) % MOD;
}
}
return -1;
}
};func strStr(haystack string, needle string) int {
n, m := len(haystack), len(needle)
if m > n {
return -1
}
const B, MOD = 131, 1000000007
pw := 1
for i := 0; i < m-1; i++ {
pw = pw * B % MOD
}
hn, hh := 0, 0
for i := 0; i < m; i++ {
hn = (hn*B + int(needle[i])) % MOD
hh = (hh*B + int(haystack[i])) % MOD
}
for i := 0; i+m <= n; i++ {
if hh == hn && haystack[i:i+m] == needle {
return i
}
if i+m < n {
hh = (hh - int(haystack[i])*pw%MOD + MOD) % MOD
hh = (hh*B + int(haystack[i+m])) % MOD
}
}
return -1
}var strStr = function(haystack, needle) {
const n = haystack.length, m = needle.length;
if (m > n) return -1;
const B = 131, MOD = 1000000007;
let pw = 1;
for (let i = 0; i < m - 1; i++) pw = pw * B % MOD;
let hn = 0, hh = 0;
for (let i = 0; i < m; i++) {
hn = (hn * B + needle.charCodeAt(i)) % MOD;
hh = (hh * B + haystack.charCodeAt(i)) % MOD;
}
for (let i = 0; i + m <= n; i++) {
if (hh === hn && haystack.startsWith(needle, i)) return i;
if (i + m < n) {
hh = (hh - haystack.charCodeAt(i) * pw % MOD + MOD) % MOD;
hh = (hh * B + haystack.charCodeAt(i + m)) % MOD;
}
}
return -1;
};function strStr(haystack: string, needle: string): number {
const n = haystack.length, m = needle.length;
if (m > n) return -1;
const B = 131, MOD = 1000000007;
let pw = 1;
for (let i = 0; i < m - 1; i++) pw = pw * B % MOD;
let hn = 0, hh = 0;
for (let i = 0; i < m; i++) {
hn = (hn * B + needle.charCodeAt(i)) % MOD;
hh = (hh * B + haystack.charCodeAt(i)) % MOD;
}
for (let i = 0; i + m <= n; i++) {
if (hh === hn && haystack.startsWith(needle, i)) return i;
if (i + m < n) {
hh = (hh - haystack.charCodeAt(i) * pw % MOD + MOD) % MOD;
hh = (hh * B + haystack.charCodeAt(i + m)) % MOD;
}
}
return -1;
}