Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1 暴力解法:如果模式串匹配失败，需要回溯到模式串的起始位置 我们想可以不用回溯到起始位置，如图：
如果能确定A==B 可以直接跳到C跟d比较 问题就转化成了如何求模式串中前缀串于后缀串相等的K个
class Solution:
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if needle =='':
return 0
nexts=self.caclNext(needle)
ans = -1
i = 0
j = 0
while i < len(haystack):
if(j==-1 or haystack[i] == needle[j]):
i += 1
j += 1
else:
j = nexts[j]
if j == len(needle):
ans = i - len(needle)
break
return ans def caclNext(self, p):
nexts = [0]*(len(p))
nexts[0] = -1
k = -1
j = 0
while j < len(p) - 1:
if k == -1 or p[j] == p[k]:
k += 1
j += 1
nexts[j] = k
else:
k = nexts[k]
return nexts