###28. Implement strStr()
题目:
https://leetcode.com/problems/implement-strstr/
难度:
Easy
先来写最符合直觉的写法：
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
i , j = 0, 0
while i < len(haystack) and j < len(needle):
if haystack[i] == needle[j]:
i += 1
j += 1
else:
i = i - j + 1 //退回j步，但是是不匹配的，我们就从下一位开始
j = 0 //j置为0
if j == len(needle):
return i - j
else:
return -1
暴力解法二：
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
if not needle:
return 0
for i in xrange(len(haystack) - len(needle) + 1):
if haystack[i] == needle[0]:
j = 1
while j < len(needle) and haystack[i+j] == needle[j]:
j += 1
if j == len(needle):
return i
return -1
利用已经部分匹配这个有效信息，保持i指针不回溯，通过修改j指针，让模式串尽量地移动到有效的位置
至此我们可以大概看出一点端倪，当匹配失败时，j要移动的下一个位置k。存在着这样的性质：最前面的k个字符和j之前的最后k个字符是一样的。
如果用数学公式来表示是这样的
P[0 ~ k-1] == P[j-k ~ j-1]
简单的证明：
因为:
当T[i] != P[j]时
有T[i-j ~ i-1] == P[0 ~ j-1]
由P[0 ~ k-1] == P[j-k ~ j-1]
必然：T[i-k ~ i-1] == P[0 ~ k-1]
好像有点理解了，比如 P 的前j个字符和 T 都匹配（匹配到i）：
-
P 中没有重复出现的字符（abcdex），那么很直觉的，我们知道不需要移动i，然后需要把 P 的j移动到0，再次开始对比。
-
P 中有重复出现的字符(abcabx)，那么也还是比较直觉的，因为 P 与 T 已经匹配上，所以说明 T 中前面也有重复出现的字符，那么我们也可以跳过重复字符的比较部分，拿着新的字符来比较。
看这两个例子：
i
|a|b|c|d|e|f|g|a|b|... T
|a|b|c|d|e|x| P
j
i
|a|b|c|d|e|f|g|a|b|... T
|a|b|c|d|e|x| P
j
这个是没有重复的例子，那么还是比较贴近我们直接的，下次比较我们会直接从 j = 0 再次开始。
i
|a|b|c|a|b|a|a|b|c|... T
|a|b|c|a|b|x| P
j
i
|a|b|c|a|b|a|a|b|c|... T
|a|b|c|a|b|x| P
j
这里有重复，同时我们也知道前面的重复部分已经匹配， 所以我们调到匹配失败但是重复开始的间隔点。
这样也和文中给的例子匹配起来了：
0 k j-k j
| a | b | c | a | b | b
k-1 j-1
这个k就是每次k需要跳回的部分。
然后到了算法部分：
好，接下来就是重点了，怎么求这个（这些）k呢？因为在P的每一个位置都可能发生不匹配，也就是说我们要计算每一个位置j对应的k，所以用一个数组next来保存，next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置。
虽然还是有点迷茫（关于next数组的部分），但是KMP AC代码如下：
class Solution(object):
def strStr(self, haystack, needle):
"""
:type haystack: str
:type needle: str
:rtype: int
"""
def getNext(p):
next = [0 for _ in range(len(p))]
next[0] = -1
j = 0
k = -1
while j < len(p) - 1:
if k == -1 or p[j] == p[k]:
j += 1
k += 1
next[j] = k
else:
k = next[k]
return next
def kmp(t, p):
i = 0
j = 0
next = getNext(p)
while i < len(t) and j < len(p) :
if j == -1 or t[i] == p[j]: # 当j为-1时，要移动的是i，当然j也要归0
i += 1
j += 1
else:
# i 不需要回溯了
# i = i - j + 1
j = next[j] # j回到指定位置
if j == len(p):
return i - j
else:
return -1
if needle:
return kmp(haystack, needle)
else:
return 0