找出字符串中第一个匹配项的下标
Find the Index of the First Occurrence in a String
本机进度仅保存在当前浏览器
题目描述
给你两个字符串 haystack 和 needle，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）；不存在则返回 -1。
示例：haystack = "sadbutsad"，needle = "sad"，输出 0；needle = "but"，输出 -1。
解题思路
- 朴素匹配逐起点比较最坏 O(n·m)；KMP 利用已匹配前缀的信息避免文本指针回退。
- 先对模式串自匹配构建 next（失配）数组：next[i] 表示模式串 [0, i] 的相等最长真前后缀长度。
- 匹配时失配则模式串指针 j = next[j-1] 跳到该前缀继续比较，文本指针 i 永不回退，整体 O(n + m)。
- 理解 next 数组的构建过程本身也是一次模式串自匹配，两段代码结构几乎一致。
参考实现
查看参考实现Python · 建议先自行作答
def strStr(haystack, needle):
n, m = len(haystack), len(needle)
# 构建 KMP 失配数组
nxt = [0] * m
j = 0
for i in range(1, m):
while j and needle[i] != needle[j]:
j = nxt[j - 1]
if needle[i] == needle[j]:
j += 1
nxt[i] = j
# 主匹配：文本指针不回退
j = 0
for i in range(n):
while j and haystack[i] != needle[j]:
j = nxt[j - 1]
if haystack[i] == needle[j]:
j += 1
if j == m:
return i - m + 1
return -1