[Leetcode]28. Implement strStr()

这是Leetcode第28题，实现strStr()函数，即在haystack中找出needle第一次出现的位置，如果不存在，那么就返回-1。
又是一个经典的算法：KMP算法，这是和之前的Manacher算法并列的两大经典算法。KMP算法本质是通过next 数组实现当模式串中的某个字符跟文本串中的某个字符匹配失配时，模式串下一步应该跳到的位置。
具体代码如下：

class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        return self.kmp(haystack,needle)

    def kmp(self,s,p):
        s_len = len(s)
        p_len = len(p)
        i,j = 0,0
        next = self.get_next(p)
        while(i<s_len and j<p_len):
            if(j == -1 or s[i]==p[j]):
                i+=1
                j+=1
            else:
                j = next[j]
        if j==p_len:return i-j
        else:return -1

    def get_next(self,p):
        next = [-1 for i in range(len(p))]
        p_len = len(p)
        k,j = -1,0
        while(j<p_len-1):
            if k==-1 or p[j]==p[k]:
                j+=1
                k+=1
                if p[j]!=p[k]:
                    next[j] = k
                else:next[j] = next[k]
            else:k=next[k]
        return next

扩展：
【Leetcode】214. Shortest Palindrome
给一个字符串(s)，在前面添加字符，求能得到的最短回文长度。
实际上是求必须包括第一个字符串的情况下，最长回文子串是多长，后面的逆序添加即可。可求 s+'#'+s[::-1] 的最长前缀后缀，其最大长度的相同前缀和后缀就是前缀的最大回文长度。这就是朴素的KMP算法中next数组得含义。之所以是朴素的，是因为上面优化后的next数组引入了出p[next[j]] = p[j] 的情况，则把 next[j] 的值再次递归。，改变了原有的含义。
具体代码如下：

class Solution:
    def shortestPalindrome(self, s: str) -> str:
        """
        :type s: str
        :rtype: str
        """
        if not s:return s
        tmp = s + '#' + s[::-1] + '*'
        next = self.get_next(tmp)
        return s[next[-1]:][::-1] + s

    def get_next(self,p):
        len_p = len(p)
        next = [-1 for i in range(len_p)]
        j,k = 0,-1
        while j<len_p-1:
            if p[j] == p[k] or k==-1:
                j+=1
                k+=1
                next[j] = k
            else:
                k = next[k]
        return next

另外，是否发现KMP的扩展与Manacher算法的扩展十分相似呢？是的，如果在字符串后面添加字符使其成为最短回文串，也可以采用KMP算法的思想，求包括最后一个字符串的情况下，最长回文子串。

参考：
从头到尾彻底理解KMP