实现KMP算法

转载自王争老师数据结构与算法之美字符串匹配基础下https://time.geekbang.org/column/article/71845

概述

字符串匹配算法，可以分为单模式串匹配算法，和多模式串匹配算法，单模式串匹配算法包括了BF（暴力匹配O(m*n)，但因为可以及早停止，实际感觉并没有很差）、RK（O(n)，n为主串长度，利用哈希加速，哈希函数要取好，不要超过int的最大值，遍历一遍主串就可以算出全部n-m+1个哈希值）、BM（Boyer-Moore，性能最好的算法，使用好后缀、坏字符，从最后一个字符开始匹配）、KMP（好前缀、坏字符）四种算法。

这里介绍不是那么复杂的KMP算法。

（PS. 其实个人觉得，要学好算法，语文非常地重要，不亚于数学，要严谨准确而清晰易懂）

思路与算法

KMP 算法基本原理

在模式串和主串匹配的过程中，把不能匹配的那个字符叫作坏字符，把已经匹配的那段字符串叫作好前缀。

当遇到坏字符的时候，我们就要把模式串往后滑动，在滑动的过程中，只要模式串和好前缀有上下重合，前面几个字符的比较，就相当于拿好前缀的后缀子串，跟模式串的前缀子串在比较。这个比较的过程能否更高效了呢？可以不用一个字符一个字符的比较了吗？

KMP 算法就是在试图寻找一种规律：在模式串和主串匹配的过程中，当遇到坏字符后，对于已经比对过的好前缀，能否找到一种规律，将模式串一次性滑动很多位？

我们只需要拿好前缀本身，在它的后缀子串中，查找最长的那个可以跟好前缀的前缀子串匹配的。假设最长的可匹配的那部分前缀子串是{v}，长度是k。我们把模式串一次性往后滑动 j - k 位，相当于，每次遇到坏字符，我们就把j更新为k，i不变，然后继续比较。

为了表述起来方便，我把好前缀的所有后缀子串中，最长的可匹配前缀子串的那个后缀子串，叫做最长可匹配后缀子串；对应的前缀子串，叫做最长可匹配前缀子串。

如何来求好前缀的最长可匹配前缀和后缀子串呢？我们发现，这个问题其实不涉及主串，只需要通过模式串本身就能求解。所以，能不能事先预处理计算好，在模式串和主串匹配的过程中，直接拿过来就用呢？

其实和BM算法（后面会讲到）类似，KMP算法可以提前构建一个数组，用来存储模式串中每个前缀（这些前缀都有可能是好前缀）的最长可匹配前缀子串的结尾字符下标。我们把这个数组定义为next数组（或者叫longest prefix suffix，最长的前缀的后缀的下标，如果到了结尾就用-1表示不存在)，很多书中还给这个数组起了一个名字，叫失效函数（failure function）。

数组的下标是每个前缀结尾字符下标，数组的值是这个前缀的最长可以匹配前缀子串的结尾字符下标。这句话有点拗口，举个例子就懂了。

有个next数组，我们很容易就可以实现KMP算法了。我先假设next数组已经计算好了，先给出KMP算法的框架代码。

def KMPSearch(p, s):
    m = len(p)
    n = len(s)

    # create lps[] that will hold the longest prefix suffix
    # values for pattern
    lps = get_lps(p, m)

    j = 0  # index for p[]
    for i in range(n):
        while j > 0 and s[i] != p[j]:
            j = lps[j - 1] + 1
        if s[i] == p[j]:
            j += 1
        if j == m:
            # print("Found pattern at index " + str(i - j + 1))
            # j = lps[j - 1] + 1
            return i - m + 1
    return -1

失效函数计算方法

基本原理剪完了，现在来看最复杂的部分，也就是next数组是如何计算的。

当然，我们可以用非常笨的方法，比如要计算下面这个模式串 b 的 next[4]，我们就把 b[0, 4]的所有后缀子串，从长到短找出来，依次看看，是否能跟模式串的前缀子串匹配。很显然，这个方法也可以计算得到 next 数组，但是效率非常低。有没有更加高效的方法呢？

我们按照下标从小到大，依次计算 next 数组的值。当我们要计算 next[i]的时候，前面的 next[0]，next[1]，……，next[i-1]应该已经计算出来了。利用已经计算出来的 next 值，我们是否可以快速推导出 next[i]的值呢？如果 next[i-1]=k-1，也就是说，子串 b[0, k-1]是 b[0, i-1]的最长可匹配前缀子串。如果子串 b[0, k-1]的下一个字符 b[k]，与 b[0, i-1]的下一个字符 b[i]匹配，那子串 b[0, k]就是 b[0, i]的最长可匹配前缀子串。所以，next[i]等于 k。但是，如果 b[0, k-1]的下一字符 b[k]跟 b[0, i-1]的下一个字符 b[i]不相等呢？这个时候就不能简单地通过 next[i-1]得到 next[i]了。这个时候该怎么办呢？

我们假设 b[0, i]的最长可匹配后缀子串是 b[r, i]。如果我们把最后一个字符去掉，那 b[r, i-1]肯定是 b[0, i-1]的可匹配后缀子串，但不一定是最长可匹配后缀子串。所以，既然 b[0, i-1]最长可匹配后缀子串对应的模式串的前缀子串的下一个字符并不等于 b[i]，那么我们就可以考察 b[0, i-1]的次长可匹配后缀子串 b[x, i-1]对应的可匹配前缀子串 b[0, i-1-x]的下一个字符 b[i-x]是否等于 b[i]。如果等于，那 b[x, i]就是 b[0, i]的最长可匹配后缀子串。

可是，如何求得b[0, i-1]的次长可匹配后缀子串呢？次长可匹配后缀子串肯定被包含在最长可匹配后缀子串中，而最长可匹配后缀子串又对应最长可匹配前缀子串又对应最长可匹配前缀子串b[0, y]。于是，查找b[0, i-1]的次长可匹配后缀子串，这个问题就变成，查找b[0, y]的最长匹配后缀子串，其中y = next[i-1]

按照这个思路，我们可以考察完所有的 b[0, i-1]的可匹配后缀子串 b[y, i-1]，直到找到一个可匹配的后缀子串，它对应的前缀子串的下一个字符等于 b[i]，那这个 b[y, i]就是 b[0, i]的最长可匹配后缀子串。

前面已经给出 KMP 算法的框架代码了，现在把这部分的代码也写出来了。这两部分代码合在一起，就是整个 KMP 算法的代码实现。

def get_lps(p, m):
    lps = [-1] * m
    k = -1
    for i in range(1, m):
        while k != -1 and p[k + 1] != p[i]:
            k = lps[k]
        if p[k + 1] == p[i]:
            k += 1
        lps[i] = k
    return lps

最后整体的实现

Python3版本

class Solution:
    def KMPSearch(self, p, s):
        # 特判
        if not p:
            return 0
        m, n = len(p), len(s)
        lps = self.get_lps(p, m)
        j = 0
        for i in range(n):
            while j != 0 and s[i] != p[j]:
                j = lps[j - 1] + 1
            if s[i] == p[j]:
                j += 1
            if j == m:
                # return i - m + 1
                print("find at {}".format(i - m + 1))
                j = lps[j - 1] + 1
        return -1

    def get_lps(self, p, m):
        lps = [-1] * m
        k = -1
        for i in range(1, m):
            while k != -1 and p[i] != p[k + 1]:
                k = lps[k]
            if p[i] == p[k + 1]:
                k += 1
            lps[i] = k
        return lps


def main():
    sol = Solution()

    s = "abcruizheuhuruizheaasdasd"
    p = "ruizhe"
    res = sol.KMPSearch(p, s)
    print(res)


if __name__ == '__main__':
    main()