Leetcode 28 : kmp算法中值得思考的两个问题

声明:

本文是为加深读者各位对于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))


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


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


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





本文为我原创

-- --
  • 投诉或建议
评论