题目
实现 strStr() 函数。给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
例：
输入：haystack = "hello", needle = "ll"
输出：2
方法一：库函数
class Solution(object):
def strStr(self, haystack, needle):
return haystack.find(needle)
方法二：KMP
- 构造 next 数组
- 判断文本串是否包含模拟串与 next 数组的构造类似。若模拟串为空，则返回 0。若模拟串不为空，需构造该模拟串的 next 数组，并初始化两个指针 p = -1 和 j = 0。若两个指针 p+1 和 j 指向的两个串的值不相同，则向前回退；若两个指针 p+1 和 j 指向的两个串的值相同，则指针 p 向右移动一位；若指针 p+1 指向模拟串的末尾，即文本串包含模拟串，输出起始位置 j-a+1。循环该步骤，每次循环指针 j 均向右移动一位，直至该指针指向文本串末尾。若不存在，则返回 -1
class Solution(object):
def strStr(self, haystack, needle):
a = len(needle)
b = len(haystack)
if a == 0:
return 0
next = self.getnext(a, needle)
p = -1
for j in range(b):
while p >= 0 and needle[p+1] != haystack[j]:
p = next[p]
if needle[p+1] == haystack[j]:
p += 1
if p == a-1:
return j-a+1
return -1
def getnext(self, a, needle): # 构造next数组
next = ['' for i in range(a)]
k = -1
next[0] = k
for i in range(1, len(needle)):
while k > -1 and needle[k+1] != needle[i]:
k = next[k]
if needle[k+1] == needle[i]:
k += 1
next[i] = k
return next
相关知识
find(str, beg, end)：
str.find()
检测字符串中是否包含子字符串 str
str：指定检索的字符串
beg：开始索引，默认为0
end：结束索引，默认为字符串的长度-
KMP：
主要思想：当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了
前缀表：记录下标 i 之前（包括 i）的字符串中，有多大长度的相同前缀后缀。它记录了模式串与主串（文本串）不匹配的时候，模式串应该从哪里开始重新匹配
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串
后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串
next 数组：可以就是前缀表，也可以是前缀表统一减一即右移一位，初始位置为 -1
next 数组构造：- 初始化：定义两个指针 i 和 j，j 指向前缀的末尾，i 指向后缀的末尾。即 j = -1，i = 1，next[0] = j = -1
- 前缀后缀不相同：s[j+1] 与 s[i] 比较，若不等，则向前回退，即 j = next[j]。当 j ≥ 0 时，不断重复此操作，直至 j <0。记录 next[i] = j，并 i 向右移动一位
- 前缀后缀相同：s[j+1] 与 s[i] 比较，若相等，则 j 向右移动一位，记录 next[i] = j，并 i 向右移动一位
例：
存在文本串 aabaabaafa 和模式串 aabaaf，对模式串 s 进行 next 数组构造
① 初始化，指针 j+1 = 0，指针 i = 1，且 next[0] = j = -1
② 由于 'a' = 'a'，那么指针 j+1 = 1，并且 next[1] = j = 0，指针 i = 2
③ 由于 'a' ≠ 'b'，那么指针 j = next[j] = next[0] = -1 ≤ 0，并且 next[2] = j = -1，指针 i = 3
④ 由于 'a' = 'a'，那么指针 j+1 = 1，并且 next[3] = j = 0，指针 i = 4
⑤ 由于 'a' = 'a'，那么指针 j+1 = 2，并且 next[4] = j = 1，指针 i = 5
⑥ 由于 'b' ≠ 'f'，那么指针 j = next[j] = next[1] = 0 ≥ 0，向左移动一位；由于 'a' ≠ 'f'，那么指针 j = next[j] = next[0] = -1 ≤ 0，并且 next[5] = j = -1
判断文本串 aabaabaafa 是否包含模式串 aabaaf，并返回模拟串出现的第一个位置
① 初始化，指针 p+1 = 0，指针 k = 1
② 第一次循环：k = 0，p+1 = 0，由于 'a' = 'a'，那么 p+1 = 1
③ 第二次循环：k = 1，p+1 = 1，由于 'a' = 'a'，那么 p+1 = 2
④ 第三次循环：k = 2，p+1 = 2，由于 'b' = 'b'，那么 p+1 = 3
⑤ 第四次循环：k = 3，p+1 = 3，由于 'a' = 'a'，那么 p+1 = 4
⑥ 第五次循环：k = 4，p+1 = 4，由于 'a' = 'a'，那么 p+1 = 5
⑦ 第六次循环：k = 5，p+1 = 5，由于 'b' ≠ 'f'，那么 p = next[4] = 1，即 p+1 = 2，由于 'b' = 'b'，那么 p+1 = 3
⑧ 第七次循环：k = 6，p+1 = 3，由于 'a' = 'a'，那么 p+1 = 4
⑨ 第八次循环：k = 7，p+1 = 4，由于 'a' = 'a'，那么 p+1 = 5
⑩ 第九次循环：k = 8，p+1 = 5，由于 'f' = 'f'，那么 p+1 = 6。又因为模拟串的长度为 6，所以返回 8-6+1 = 3，3 为模拟串出现的第一个位置
参考
find函数：https://www.runoob.com/python3/python3-string-find.html
KMP：https://programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html
