Find the First Occurrence in a String
你会得到两个字符串，haystack 和 needle。返回 needle 在 haystack 中第一次出现的位置索引，从 0 开始计数。如果 needle 从未出现在 haystack 中，则返回 -1。请自己编写搜索逻辑，不要调用内置的子字符串搜索方法，例如 find 或 indexOf。
函数
- haystackstring
- 要搜索的文本
- needlestring
- 要查找的字符串
- 返回值integer
- needle 第一次出现的位置索引；如果没有，则为 -1
约束条件
1 ≤ haystack.length ≤ 5 × 1041 ≤ needle.length ≤ 5 × 104- 两个字符串都只包含小写英文字母。
needle可能比haystack长。这样一来，它就不可能出现，答案是-1。
示例
- 输入
- haystack = "bananarama"needle = "ana"
- 输出
- 1
- 解释
- 索引 1 到 3 处的字母拼成了
ana。另一处副本从索引 3 开始，与它重叠，但只计算第一个副本，所以答案是 1。
- 输入
- haystack = "pineapple"needle = "apples"
- 输出
- -1
- 解释
apple从索引 4 开始，但 haystack 紧接着就结束了，所以 needle 最后的s没有可匹配的内容。答案是-1。
- 输入
- haystack = "abcabcabd"needle = "abcabd"
- 输出
- 3
- 解释
- 从索引 0 开始的尝试匹配了
abcab，接着遇到一个c，而目标字符串需要的是d。从索引 3 开始的副本匹配了全部 6 个字母。
进阶
你能在 O(n + m) 时间内，返回 needle 每次开始的位置索引吗？包括彼此重叠的匹配。
提示
逐个打开提示，每个都会多透露一点。
needle的副本只能从一个仍能完整放入haystack的索引处开始。最后一个这样的索引是多少？当较长的部分匹配失败时，暴力算法会从下一个索引重新开始，并再次读取大部分相同的字母。你已经匹配的字母是
needle的前缀，因此不用再次查看 haystack，你也知道这些字母。对于
needle的每个前缀，预先计算既是其后缀又是其真前缀的最长部分的长度。只扫描一次 haystack，并用计数k记录已匹配字母的数量；发生不匹配时，将k缩小到预先计算的长度，而不是在 haystack 中回退。
题解
检查每个起始位置是正确的，但如果部分匹配在接近末尾时失败，这部分匹配就会被丢弃，接下来从下一个起始位置重新读取相同的字母。Knuth-Morris-Pratt 算法会保留这些工作：根据 needle 构建的表会指出，失败的匹配中有多少部分仍然有效，因此扫描过程不会回退，并且运行时间为 O(n + m)。
检查每个起始位置
结果正确，但无法在最大的测试中运行完毕
思路
将长度分别称为 n 和 m。副本可以从索引 0 到 n-m 中的任意位置开始；再往后开始就会超出末尾。从左到右尝试各个起始位置，逐个比较字母，直到出现第一个不同的字母。第一个完全匹配的位置就是副本所在的位置。如果查找串比被查找串更长，就没有可尝试的起始位置。
一个由 50,000 个 a 组成的被查找串，以及一个由 24,999 个 a 后接一个 b 组成的查找串，会产生 25,001 个起始位置，每个位置要进行 25,000 次比较：总比较次数超过 6 × 10^8，结果却是 -1。
算法
- 设
n和m分别为haystack和needle的长度。 - 对于从 0 到
n-m的每个start，将j设为 0。 - 当
j < m且haystack[start + j]等于needle[j]时，增加j。 - 如果
j达到m，说明所有字母都匹配：返回start。 - 如果没有可行的起始位置，返回
-1。
def strStr(haystack, needle):
n, m = len(haystack), len(needle)
for start in range(n - m + 1):
j = 0
while j < m and haystack[start + j] == needle[j]:
j += 1
if j == m:
return start
return -1Knuth-Morris-Pratt
思路
在 abcabcabd 中查找 abcabd 时，从索引 0 开始的尝试匹配了 abcab，随后失败。这些字母以 ab 结尾，而这正是 needle 的开头，因此下一次有效尝试已经匹配了两个字母，你可以从 haystack 中的同一位置继续。
字符串的边界是一个较短的前缀，同时也是后缀，例如 abcab 中的 ab。lps[i] 是 needle[0..i] 的最长边界的长度；对于 abcabd，它是 [0, 0, 0, 1, 2, 0]。匹配了 k 个字母后发生不匹配时，将 k 减少到 lps[k-1]，然后再次比较同一个字母。不会跳过任何一次匹配：从失败尝试内部开始的匹配，其开头必定是已匹配部分的一个边界，并且会先尝试最长的边界。
k 对 haystack 中的每个字母最多增加一次，而每次回退都会使它减小，因此扫描最多需要 2n 步。
算法
- 构建
lps：令k = 0，对于从 1 到m-1的i，当k > 0且needle[i] != needle[k]时，令k = lps[k-1]；匹配时增加k；存储lps[i] = k。 - 将
k重置为 0，然后用索引i遍历 haystack。 - 当
k > 0且haystack[i] != needle[k]时，令k = lps[k-1]。 - 如果
haystack[i]等于needle[k]，则增加k。 - 如果
k等于m，则返回i-m+1。如果循环结束，则返回-1。
def strStr(haystack, needle):
m = len(needle)
# lps[i]: length of the longest proper prefix of needle[0..i] that is also its suffix
lps = [0] * m
k = 0
for i in range(1, m):
while k > 0 and needle[i] != needle[k]:
k = lps[k - 1]
if needle[i] == needle[k]:
k += 1
lps[i] = k
k = 0 # how many letters of needle are matched so far
for i, ch in enumerate(haystack):
while k > 0 and ch != needle[k]:
k = lps[k - 1] # fall back to the longest border, never move i back
if ch == needle[k]:
k += 1
if k == m:
return i - m + 1
return -1
易错点和边界情况
- 让循环从
n-1开始，而不是n-m。当主串的末尾与模式串的开头匹配时，比较会越过末尾。 - 当模式串更长时，使用无符号长度计算
n-m（C++ 中的size_t，Rust 中的usize）：C++ 会回绕成一个很大的数，Rust 则会在调试构建中触发 panic。先检查m > n。 - 将 KMP 回退写成
if，而不是while。在aabaa中搜索aaa时，遇到b需要回退两次；只回退一次，就会错误地报告在索引 2 处找到副本。 - 失配后回退主串索引。只有
k会改变；移动i回去会让复杂度重新变成O(n · m)。 - 在 Lua 或 R 中返回从 1 开始的索引。
常见问题3
查找字符串第一次出现的位置的时间复杂度是多少？
在最坏情况下，检查每个起始位置需要 O(n · m) 的时间和 O(1) 的额外空间，其中 n 和 m 分别是 haystack 和 needle 的长度。Knuth-Morris-Pratt 算法需要 O(n + m) 的时间，并需要 O(m) 的空间来存储其表。
如何构建 KMP 前缀表？
在针自身上运行匹配循环。让 i 从 1 开始遍历，将 k 保持为当前边界长度；如果不匹配，就通过 k = lps[k-1] 回退，并将 k 存入 lps[i]。对于 aabaaab，表格为 [0, 1, 0, 1, 2, 2, 3]。
你能用哈希而不是 KMP 来解决它吗？
可以，使用 Rabin-Karp。为 haystack 中每个包含 m 个字母的窗口维护一个滚动哈希值，窗口滑动时以常数时间更新。只有当它与 needle 的哈希值相等时，才比较字母。预期运行时间为 O(n + m)；如果发生大量哈希冲突，运行时间会趋近于 O(n · m)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def strStr(haystack, needle):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
haystack = "bananarama" needle = "ana"
预期输出
1