【力扣28. 实现 strStr()】KMP算法（Python3）

题目描述

https://leetcode-cn.com/problems/implement-strstr/

思路题解

运用KMP算法

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        def getNext(p):
            n=len(p)
            next=[-1]*n
            j,k=0,-1
            while j<n-1:
                if (k>=0 and p[j]==p[k]) or k==-1:
                    k += 1
                    j += 1
                    if p[j]==p[k]:next[j]=next[k]
                    else:next[j]=k
                else:
                    k=next[k]
            return next
        n1,n2=len(haystack),len(needle)
        next=getNext(needle)
        # print(n1,n2)
        i,j=0,0
        while i<n1 and j<n2:
            # print(i, j)
            if haystack[i]==needle[j] or j==-1:
                i+=1
                j+=1
            else:
                j=next[j]
        # print(i,j)
        if j == n2:
            return i - j
        return -1

KMP算法

0、算法详解

KMP算法详解-彻底清楚了(转载+部分原创)

当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]

next数组的定义：next[j] = k，表示当T[i] != P[j]时，j指针的下一个位置。另一个非常有用且恒等的定义，因为下标从0开始的，k值实际是j位前的子串的最大重复子串的长度。

1、求next数组：

基础版：

def getNext(p):
    n=len(p)
    next=[-1]*n
    j,k=0,-1
    while j<n-1:
        if (k>=0 and p[j]==p[k]) or k==-1:
            k += 1
            j += 1
            next[j]=k
        else:
            k=next[k]
    return next

优化版：

def getNext(p):
    n=len(p)
    next=[-1]*n
    j,k=0,-1
    while j<n-1:
        if (k>=0 and p[j]==p[k]) or k==-1:
            k += 1
            j += 1
            if p[j]==p[k]:next[j]=next[k]
            else:next[j]=k
        else:
            k=next[k]
    return next

2、 求子串开始的位置

n1,n2=len(t),len(p)
next=getNext(p)
i,j=0,0
while i<n1 and j<n2:
    if t[i]==p[j] or j==-1:
        i+=1
        j+=1
    else:
        j=next[j]
if j == n2:
    return i - j
return -1