Leetcode 28 : ｋｍｐ算法中值得思考的两个问题

声明：

本文是为加深读者各位对于kmp算法的理解，重心不在讲解具体的题解代码，

故阅读本文前需要对于kmp有一定了解

kmp算法因为其效率高，而被广泛运用在各种领域，具有重要意义

其原理理解起来较为简单，而实现过程却不然

许多文章对于其原理阐述十分详尽，却忽略对于对于初学者疑惑的解答

写此文以鼓励正在自学或者初学的朋友独立思考，也作抛砖引玉

转载需附作者Id及原作品链接

以下图的文本串与模式串为例，

在第一个X处出现第一次失配，对应的最长公共前后缀为ABC

kmp的核心就是避免回溯，按照正确做法，需将前缀移至后缀位置

即下图所示，直接跳过对于中间位置的判断，从而提高效率

考虑第一个问题，公共前后缀之间是否存在满足条件的位置

如下图所示，中间位置也可以出现公共前后缀

答案是否定的，根据最长公共前后缀的定义，

若最终模式串可以在中间位置与文本串匹配，

则说明存在比ABC(最长公共前后缀)更长的公共前后缀，显然矛盾

通过反证法，成功验证跳过的做法的可行性

kmp 核心步骤为Next数组的求导，

若采用暴力枚举的方法，显然违背kmp算法的初衷，

事实上，可利用动态规划的思想，动态的求出Next数组

以模式串P = ABAABAA为例，

规定 Next (0) = None，L为当前公共前后缀长，i为后缀索引

显然有以下等式成立，

Next (1) = 0，Next (2) = 0，Next (3) = 1，Next (4) = 1，Next (5) = 2

通过代码实现以上过程并非难事，关键在于求导 Next (6) = 2

当 P(3) != P(6) 时，不能简单认为 Next (6) = 0

实际上当 i == 6 时，仍有可能存在公共前后缀

易知此时的公共前后缀一定小于等于 Next (5)，

并且此时公共前后缀就隐藏在之前的公共前后缀之中

这也就是问题的关键，也即是 L = Next(L-1) 操作的理由

可通过图像加深理解，如下如图所示，此时X处与Y处失配，即当前L 与 i 的位置失配

假设失配后仍然存在最长公共前后缀，如下图所示

从左至右，将三段相同的黄色区间分别记为①，②，③，

不难理解此情况下，①，③分别为此情况下的公共前后缀，

下面考虑区间 ② 出现的原因，

由于前缀与后缀相等，所以在前缀串的相同的相对位置也会出现相同的区间，

同时考虑区间①，②，发现恰好符合最长公共前后缀定义，即 Next (L-1)

因此，只需检查 ？所在位置的字符是否为Y，

若为Y，则已经找到当前情况下的最长公共前后缀

若不为Y，则如下图所示

依照以上的思路继续检查，以循环的形式进行，

不断缩小检查的范围，直至再无最长公共前后缀可供检查

通过对以上两个问题的思考，可以加深对于kmp算法的理解，

深入思考需要时间，也需要精力，但也会人让收获更多

下面通过代码更进一步加深理解，以 Leetcode.28 为例

代码如下：

class Solution(object):

    def strStr_0(self,haystack,needle):

    # 暴力搜素

        n=len(haystack)

        m=len(needle)

        if n==0:return 0

        if n<m:return -1

        for i1 in range(n):

            if haystack[i1]!=needle[0]:continue

            for i2 in range(m):

                if i1+i2==n:return -1

                if haystack[i1+i2]!=needle[i2]:break

            else:return i1

        return -1

    def strStr_1(self,haystack,needle):

    # KMP 算法

        n=len(haystack)

        m=len(needle)

        if n<m:return -1

        if not n:return n

        if not m:return m

        def getTable(string):

            s=len(string)

            memory=[0]*s

            i=1

            l=0

            while i<s:

                if string[i]==string[l]:

                    l+=1

                    memory[i]=l

                    i+=1

                else:

                    if l==0:

                        i+=1

                    else:

                        l=memory[l-1]            

            result=[None]+memory[:-1]

            return result

        prefixTable=getTable(needle)

        i1=i2=0

        while i1<n:

            if i2==m-1 and haystack[i1]==needle[i2]:

                return i1-m+1

            if haystack[i1]==needle[i2]:

                i1+=1

                i2+=1

            else:

                i2=prefixTable[i2]

                if i2==None:

                    i1+=1

                    i2=0

        return -1

if __name__=='__main__':

    haystack="ccaaaaabaaabaaac"

    needle  ="aaaaabaaab"

    haystack="aabaaabaaac"

    needle="aabaaac"

    sl=Solution()

    print(sl.strStr_0(haystack,needle))

    print(sl.strStr_1(haystack,needle))

此栏目预测共享自学之乐，共勉求知之友，共塑网站和谐好学的氛围。

欢迎大家在评论区发表合理的意见和指正。

如果觉得该栏目对您有帮助，望不吝点赞收藏。