题目描述
对于一个给定的 source 字符串和一个 target 字符串，你应该在 source 字符串中找出 target 字符串出现的第一个位置(从0开始)。如果不存在，则返回 -1。
测试样例
输入: source = "source" ， target = "target"
输出:-1
样例解释: 如果source里没有包含target的内容，返回-1
输入: source = "abcdabcdefg" ，target = "bcd"
输出: 1
样例解释: 如果source里包含target的内容，返回target在source里第一次出现的位置
思路与KMP算法说明
通常的解法会有O(n2)的复杂度，使用KMP算法能达到O(n)复杂度，这里就举个例子来说明下KMP是如何work的吧。
如下图，此时source字符串为ABCABCDHIJK，称为主串，target字符串为ABCE，称为模式串，它们的字符位置指针分别为i和j，依次判断主串在位置i和模式串在位置j的字符是否一样，如果是，则i和j都向前移动。
OK，这样做之后我们会来到下图这种情况，此时主串在位置i和模式串在位置j不匹配了，那么我们下一步该如何呢？
如果是暴力解法，下一步应该会变成下图这种情况：
但是，仔细想想，这样很蠢啊，因为在之前的匹配过程中，已经知道了主串和模式串在前三个字符（ABC）是按序匹配的了，并且这三个字符没有重复，那么主串的第二个字符（B）和模式串的第一个字符（A）肯定不会匹配！
进一步，i不需要往回移动，因为主串在匹配失败的位置（第4个字符）前只有一个A，而移回去是要和模式串第一个字符A进行匹配的，所以根本不可能成功匹配。另外，即使在匹配失败时的位置i前面有多个A，也不需要移回去，只需将模式串的第一个字符移到主串不是第一个A的另外那个A的位置进行对齐，然后在当前i位置再次进行匹配即可。
对于上面这个例子，基于前面的匹配结果，下一次进行匹配的情况应该如下：
通过上面的例子，我们知道了i在不匹配时是不需要往回移的，那么现在问题就在于j应该如何移动了。
再来个例子，如下图，上面的是主串，下面的是模式串。
当前匹配失败后，会来到下图的情况：
仔细观察下，不知你有无发现其中的小秘密？
记现在j来到的位置为2（从0开始计数），刚刚j是在第5位匹配失败的，而第5位的前面2个数（最后一个B前面的AB）和位置2前面的数（模式串最前面的AB）是相同的！
引申开来，当模式串在位置j匹配失败时，记j要移动到的下一个位置为k，则存在着这样的性质：模式串最前面的k个字符和位置j之前的k个字符是一样的。
这样一来，当主串在位置i与模式串在位置j匹配失败时，我们就将j移动到k，与主串在位置i继续匹配，而无需再对模式串在位置0, 1, .., k-1进行判断了，因为它们一定是与主串在i前面的k个位置即位置i-k, i-k+1, .., i-1匹配的！
什么鬼..或许现在你会觉得有点懵，没关系，一起来推导一波：
记主串和模式串分别为T和P，假设现在两者在位置i和j匹配失败，而前面的字符都匹配成功，那么则有：
T[i-j, i-j+1, .., i-1] == P[0, 1, .., j-1] 且 T[i] != P[j]
基于上述分析，此时j需要移动到的位置k，有如下性质：
P[0, 1, .., k-1] == P[j-k, j-k+1, .., j-1]
于是，必有：
T[i-k, i-k+1, .., i-1] == P[0, 1, .., k-1]
通过以上，已经把j如何移动的问题给解决了，KMP的核心部分也就基本搞定了。
嗯，是的，只是“基本”，因为还有个小问题，基于上述流程去处理的话，有可能j移动到k后会发现模式串在位置j和k的字符其实一样的，这就很尴尬了，相当于做了无用功，因为我当前在位置j匹配失败，因而移动到位置k，但你却给我来个和刚刚一样的字符，搞笑么...
因此，记录j在匹配失败时应该移动到的位置k时，需要外加一个判断条件，就是模式串在j和k位置的字符是否相等，如果相等，那么j下一步需要移动到的位置实际上等同于模式串在位置k与主串在位置i匹配失败时要移动到的位置。
到此，KMP的核心流程算是基本搞定了，嗯？你问我怎么还是“基本”，因为还没上代码啊...话不多说，赶紧上菜！
代码
class Solution:
"""
@param source:
@param target:
@return: return the index
"""
def strStr(self, source, target):
# Write your code here
# 主串或目标字符串为None或者主串中不存在目标字符串
if source is None or target is None or target not in source:
return -1
# 目标字符串是空字符串或与主串相等
if not target or source == target:
return 0
'''KMP算法'''
i = j = 0
# 计算目标字符串在每个位置与主串匹配失败后
# 指针应该移动到的下一个位置
next_pos = self.get_next(target)
while i < len(source) and j < len(target):
if j == -1 or source[i] == target[j]:
i += 1
j += 1
else:
j = next_pos[j]
if j == len(target):
return i - j
else:
return -1
def get_next(self, p):
"""
@param p: pattern string of KMP;
@return: the next position outputs
"""
next_pos = {0: -1}
k, j = 0, 1
while j < len(p):
if k == 0 or p[j - 1] == p[k - 1]:
if p[j] != p[k]:
# p[0,..,k-1] == p[j-k,..,j-1]
# 且p[k] != p[j]
# 因此模式串p在位置j匹配失败时
# 下一个位置就是k
next_pos[j] = k
else:
# 若模式串在j和k这个位置有相同字符，
# 则代表p[0,..,k] == p[j-k,..,j]
# 那么在位置p匹配失败时的下一个位置
# 等同于在位置k匹配失败时的下一个位置
next_pos[j] = next_pos[k]
k += 1
j += 1
else:
# p[0,..,k-1] != p[j-k,..,j-1]
# 那么k需要往前移动，变为模式串在
# 位置k匹配失败时要移动到的下一个位置
k = next_pos[k]
return next_pos
附：
其实这题还有个“偷工减料”的解决方法，代码量也非常少...
class Solution:
"""
@param source:
@param target:
@return: return the index
"""
def strStr(self, source, target):
# Write your code here
if source is None or target is None or target not in source:
return -1
if not target:
return 0
return len(source.split(target)[0])
其实几乎就是一行代码 len(source.split(target)[0])，哈哈哈，有些人可能会发牢骚，一行代码解决的事情为啥喷那么多口水。
Em..因为我觉得，虽然几乎所有事情都以结果论成败，但是中间的过程却是十分重要的，真正能帮助你成长的也是过程，学习更当如此，在过程中你才能体会到与知识相关的思想，从而有所感悟，接着汲取其中之长，转化为自己所有，再结合所遇情境，加以适当改进，最终实践于生活。
有关KMP算法更详细地讲解可以参考这篇文：https://blog.csdn.net/qq_41661809/article/details/81415687
