KMP 算法

题目描述:Leetcode 28. Implement strStr()

之前在 Leetcode 上 AC 的 O(MN) 版本:Q28 Implement strStr()

解题思路:

KMP 算法是经典的求解子串(模式串)出现在主串中位置的算法,也是数据结构当时学习的一个知识点。它因为在匹配过程中,主串下标不后退,而可以使时间复杂度从 O(MN) 降为 O(M+N) 。之前学过忘了,现在在此做一个总结。

KMP 算法的关键:求出子串(模式串)的 next 数组。

举例:

子串 pattern 下标       0  1  2  3  4  5  6  7  8  9  10 11 12
子串 pattern            a  b  c  d  a  z  a  a  a  b  c  a  b
其对应的 next 数组为     0  0  0  0  1  0  1  1  1  2  3  1  2

举例理解 next : 第 2 个 ‘b’ 对应的 next[9] = 2 ,其意义为从 ‘b’ 往前数,找到一个和从首字符开始相等的最长子串(‘ab’)。而第 2 个 ‘c’ 对应 next[10] = 3,是因为从 ‘c’ 往前数,可以找到的与首字符开始数的相等的最长子串为 ‘abc’。其他同理。

如何求解 next 数组?

  1. 构造一个与子串长度相等大小的数组,初始化为 0;
  2. 还是以第 2 个 ‘b’ 对应的 next[9] 为例,next[9] = 2 是怎么计算出来的呢?是因为前一个已经求得的 next[8] = 1 对应的字符 pattern[1] 刚好也为 ‘b’ ,因此我们直接在 next[8] = 1 基础上加1即可得到 next[9] = 2;第 2 个 ‘c’ 对应 next[10] = 3 的求解也是同理。
  3. next[8] = 1 怎么求解呢?我们发现 next[7] = 1对应的字符 pattern[1] = ‘b’,不等于 ‘a’,此时我们将在 next[next[7]-1] 中继续找(这里是一个循环),发现 next[0] = 0 对应的字符 pattern[0] = ‘a’,这回相等了,我们就在 next[0] = 0 基础上加1即可得到 next[8] = 1。
  4. next[2] = 0 怎么求解的呢?我们发现 next[1] = 0 对应的字符 pattern[0] = ‘a’,不等于 ‘c’,此时我们将在 next[next[1]-1] 中继续找(但是此时 next 下标已经小于0了,表明从最开始也没有找到匹配的最长子串),next[2] 直接赋为 0 即可。
  5. 循环一遍即可找到所有字符对应的 next[i] 值。

如何利用 next 数组进行匹配?

简单来说,遍历主串,一个一个匹配,如果相等,主串和子串都向后移动一位,记录匹配的长度加 1;如果匹配失败,则主串的下标不变,子串的下标变为失配字符的前一个 next 数组的值,即 j = next[j-1],同时,匹配的长度要更新为 j 而不是 0,因为前 j 个字符是匹配的。如果失配的字符下标 j = 0(下面例子的第四次匹配),说明从头都没有找到最长子串,这时主串的下标要加1,从下一个字符开始找,不然会陷入死循环。

可以结合下面这个例子理解上面这段话的匹配过程:

子串的下标           0  1  2  3  4  5  6  7  8  9
子串 pattern        a  b  c  d  a  a  b  c  a  b
子串的 next 数组     0  0  0  0  1  1  2  3  1  2
Python 实现:
class Solution:
    # KMP 算法
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        # 边界情况处理
        if len(needle) == 0: 
            return 0
        if len(haystack) < len(needle):
            return -1
        # 产生 next 数组
        next = self.nextArr(needle)
        # print(next)
        i = j = 0
        length = 0
        while i < len(haystack):
            if haystack[i] != needle[j]:
                if j == 0:  # 到头还是无法匹配
                    i += 1
                else:
                    j = next[j-1]
                length = j # 已经比较过的长度
            else:
                length += 1
                i += 1; j += 1
            if length == len(needle):
                return i - length
        return -1  # 未找到

    # 求 next 数组
    def nextArr(self, needle):
        lens = len(needle)
        next = [0] * lens
        for i in range(1, lens):
            preNextVal = next[i-1]
            while preNextVal > 0 and needle[i] != needle[preNextVal]:
                preNextVal = next[preNextVal-1]
            if needle[i] == needle[preNextVal]:
                preNextVal += 1
            next[i] = preNextVal
        return next

# next 数组验证
print(Solution().nextArr('abcdazaaabcab')) # [0, 0, 0, 0, 1, 0, 1, 1, 1, 2, 3, 1, 2]
print(Solution().nextArr('abababzabababa')) # [0,0,1,2,3,4,0,1,2,3,4,5,6,5]

# 子串匹配 Test1
haystack = 'ababcdaabccabcdaabcab'
needle = 'abcdaabcab'  # 对应的 next = [0, 0, 0, 0, 1, 1, 2, 3, 1, 2]
print(Solution().strStr(haystack, needle)) # 12

# 子串匹配 Test2
haystack = "ississip"
needle = "issip"   # 对应的 next = [0,0,0,1,0]
print(Solution().strStr(haystack, needle)) # 3

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Python爬虫与算法进阶

Python实现常见的回文字符串算法

Manacher 算法首先对字符串做一个预处理,使得所有的串都是奇数长度, 插入的是同样的符号且符号不存在与原串中,串的回文性不受影响

20740
来自专栏静默虚空的博客

字符串 模式匹配

要点 模式匹配是数据结构中字符串的一种基本运算,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串,这就是模式匹配。 假设P是给定的子串,T是待查找的字...

25580
来自专栏海天一树

小朋友学算法(6):求幂pow函数的四种实现方式

在math.h中,声明了一个函数pow(x, n),用于求x的n次方。 假如咱们不调用math.h中的pow函数,如何实现求x ^ n的算法呢?

25920
来自专栏测试开发架构之路

程序员面试50题(1)—查找最小的k个元素[算法]

题目:输入n个整数,输出其中最小的k个。例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。 分析:这道题最简单的思路莫过于把输...

34690
来自专栏desperate633

LintCode 尾部的零题目分析代码

例子:(1000的阶乘末尾0的个数)**** 1000 / 5 + 1000 / 25 + 1000 / ...

9220
来自专栏LhWorld哥陪你聊算法

【推荐系统篇】--推荐系统之测试数据

20120
来自专栏C/C++基础

华为2017校招C++岗笔试题

输入两个字符串M和N,从字符串M中删除字符串N中所有的字符。例如,输入”abcda”和”ac”,则删除之后的第一个字符串变成”bd”。

72410
来自专栏数据结构与算法

后缀自动机经典操作

21940
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

43220
来自专栏章鱼的慢慢技术路

解密回文——栈

16230

扫码关注云+社区

领取腾讯云代金券