KMP算法
今天在做字符串匹配的问题的时候想起了KMP算法。真的很难理解，所以在这里进行一个整理。
KMP算法在字符串不匹配的时候提供了一种简单的方式，使得模式串不需要从头去遍历。
例如:
待匹配串s： aabaaf 使用i去遍历
模式串t：aabaab 使用j去遍历
我们使用for循环遍历i和j为5的时候，发现s[i] != s[j]，此时j需要回退到j = 2的位置。因为s和t有相同的字符串aa。
那么如何使得j回退到正确的位置，这里我们需要使用最长相等前后缀，用next来表示。
- 前缀：带首字母不带尾字母的连续子串
- 后缀：带尾字母不带首字母的连续子串
以以下字符串为例进行介绍：
a：没有最长相等前后缀, 0
aa: 前缀a等于后缀a，最长相等前后缀1
aab：后缀末尾b无匹配，0
aaba：前缀a等于后缀a，最长相等前后缀1
aabaa：前缀aa等于后缀aa，最长相等前后缀2
aabaab：前缀aab等于后缀aab，最长相等前后缀3
综上，当模式串是aabaab时，前缀表next = [0,1,0,1,2,3]。当我们发现aabaaf中指针指向f的时候不符合要求（不等于b），那我们就需要寻找前一位的next[4] = 2，查看相同的前缀（也就是aa）的后一位，指向2位置进行进一步的对比。
代码实现如下。其中，j表示为最长相等前后缀的后一个位置（方便进行比较），也是其长度。
- 对于
needle[i] == needle[j]，j的左侧位置中具有与j右侧某处到i相同的字符串（j为0时就是没有），此时j找后一个位置j += 1。然后next[i] = j。 - 当
needle[i] ！= needle[j]，因为是连续字符串，就需要往前找。j找它前一个位置的最长相等前后缀的后一位置（表示为next[j - 1]），看看那个位置的元素是否与needle[i]相等。不相等继续往前找，直到j = 0。这个思路与上面aabaaf和aabaab不匹配时候的查找方式相似。
def getNext(needle):next = [0] * len(needle)j = 0for i in range(1, len(needle)):while j > 0 and needle[i] != needle[j]:j = next[j - 1]if needle[i] == needle[j]:j += 1next[i] = jreturn next
完整代码如下：
class Solution:def strStr(self, haystack: str, needle: str) -> int:def getNext(needle):next = [0] * len(needle)j = 0for i in range(1, len(needle)):while j > 0 and needle[i] != needle[j]:j = next[j - 1]if needle[i] == needle[j]:j += 1next[i] = jreturn nextnext = getNext(needle)j = 0for i in range(len(haystack)):while j > 0 and haystack[i] != needle[j]:j = next[j - 1]if haystack[i] == needle[j]:j += 1if j == len(needle):return i - len(needle) + 1return -1
