【KMP算法最详细讲解】28. 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

思路：KMP算法

KMP的经典思想就是: 当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。

next数组：前缀表：记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀表是用来回退的，它记录了当模式串与主串不匹配的时候，模式串应该从哪里和主串重新匹配。

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

举个例子：

比如：

模式串：aabaabaaf

字符串：aabaaf

前面匹配了aabaab和aabaaf，发现最后一位不匹配，这个时候，我们知道，前一位也就是aabaa的最后一个a，它对应数字2，就是说最后两个单位长度的后缀，是和它的前缀一样的。所以我们只需要从aabaa的倒数第二个元素对应的原字符串的位置重新开始找。

相当于是，我们发现f这个位置不匹配了，但我们之前f前面的aa，和子串的前两位aa，是一样的，所以子串从它后两位aa对应的长串的位置，重新看aa后面的b与长串aa的后面是不是对应就可以了。

时间复杂度分析：

其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。

生成next数组的过程讲解：

class Solution:
    def getNext(self, next, s):
        j=-1
        next[0] = j
        for i in range(1, len(s)):
            while j>=0 and s[i] != s[j+1]:
                j=next[j]
            if s[i] == s[j+1]:
                j += 1
            next[i] = j


    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0
        next = [0] * len(needle)
        self.getNext(next, needle)
        j = -1
        for i in range(len(haystack)):
            while j >= 0 and haystack[i] != needle[j+1]:
                j = next[j]
            if haystack[i] == needle[j+1]:
                j += 1
            if j == len(needle) - 1:
                return i-len(needle)+1
        return -1

这道题还挺难的。以后还需要时常复习和思考。