28. Implement strStr()(KMP字符串匹配算法)

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个

 1 class Solution:
 2     def strStr(self, haystack, needle):
 3         """
 4         :type haystack: str
 5         :type needle: str
 6         :rtype: int
 7         """
 8         if needle =='':
 9             return 0
10         nexts=self.caclNext(needle)
11         ans = -1
12         i = 0
13         j = 0
14         while i < len(haystack):
15             if(j==-1 or haystack[i] == needle[j]):
16                 i += 1
17                 j += 1
18             else:
19                 j = nexts[j]
20             if j == len(needle):
21                 ans = i - len(needle)
22                 break
23         return ans
24 
25     def caclNext(self, p):
26         nexts = [0]*(len(p))
27         nexts[0] = -1
28         k = -1
29         j = 0
30         while j < len(p) - 1:
31             if k == -1 or p[j] == p[k]:
32                 k += 1
33                 j += 1
34                 nexts[j] = k
35             else:
36                 k = nexts[k]
37         return nexts