字符串匹配 - KMP算法
实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1
- 示例1:
输入: haystack = "hello", needle = "ll" 输出: 2
- 示例2:
输入: haystack = "aaaaa", needle = "bba" 输出: -1
题解
阮一峰： http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
写的非常不错，容易懂，博主这边就不做多解释，这边贴一下例子就行
实现代码
- Python
class Solution: def strStr(self, haystack: str, needle: str) -> int: if len(needle) == 0: return 0 next = self.next_list(needle) i = 0 j = 0 ans = -1 n = len(haystack) while i < n: if haystack[i] == needle[j] or j == -1: i += 1 j += 1 else: j = next[j] if j == len(needle): ans = i - j break return ans # 用来生成next数组，判别最长相同前后缀 def next_list(self, needle): n = len(needle) k = -1 i = 0 next = [0 for i in range(n)] next[0] = -1 while i < n-1: if needle[i] == needle[k] or k == -1: i += 1 k += 1 next[i] = k else: k = next[k] return next
