KMP算法

August 2018 2 minute read

综述

KMP算法是一种字符串搜索算法,它解决的是从一个字符s1中找到字符串s2所在位置(如果不在则返回-1)。

在Python中的String类型的find方法,就是字符串搜索算法的一个例子(虽然它的实现不是KMP算法)

>>"test123dd".find("123d")
>>4
>>"test123dd".find("apple")
>>-1

暴力解法

对于字符串搜索算法,最容易想到的自然是暴力匹配,即从s1的第0位,一直匹配到最后一位。代码如下:

def bruteforce_match(s1: str, s2: str)->int:
    if s1 == None or s2 == None or len(s2) < 1 or len(s1) < len(s2):
        return -1
    i = j = 0
    while i < len(s1) and j < len(s2):
        if s1[i] == s2[j]:
            j = j + 1
        else:
            j = 0
        i = i + 1

    if j == len(s2):
        return i - j
    else:
        return -1

这样的逻辑虽然简单,但是时间复杂度很高,为O(m*n)

KMP算法

KMP算法分为两步:

计算next数组

next数组的定义是: 对字符串s2的每一位都求一个整数n<len(s2),使得s[n]最长前缀等于最长后缀,且前缀不包含s[n]前的最后一个字符,后缀不包含第一个字符(不能取整体),如果没有前缀n=-1,如果前缀就是后缀n=0.

def find_next(s: str)->[int]:
    if len(s) == 1:
        return [-1]
    result = [0 for i in range(len(s))]
    result[0] = -1
    result[1] = 0
    i = 2
    cn = 0
    while i < len(result):
        if s[i-1] == s[cn]:
            cn += 1
            result[i] = cn
        elif cn > 0:
            cn = result[cn]
        else:
            result[i+1] = 0
        i = i + 1
    return result

通过next数组,找到字符串s2在字符串s1中的位置

有了next数组之后,我们依旧从s1字符串的第一位开始做匹配。

假设i和j为0,根据匹配结果不同,有下面三种情况:

  1. 如果匹配s1的i位和s2的j位相同,则匹配i+1和j+1位

  2. 匹配结果不同,且next数组的j位为-1,说明在s2的第一位,则匹配s1的i位和s2的j+1位

  3. 匹配结果不同,next数组的j位不为-1,则让j等于next[j]

如果到最后发现j<len(s2),说明没有匹配到s2,即s1中不存在s2,返回-1.

def kmp(s1: str, s2: str)->int:
    if s1 == None or s2 == None or len(s2) < 1 or len(s1) < len(s2):
        return -1
    next_arr = find_next(s2)
    i = j = 0
    while i < len(s1) and j < len(s2):
        if s1[i] == s2[j]:
            i = i + 1
            j = j + 1
        else:
            if next_arr[j] == -1:
                i = i + 1
            else:
                j = next_arr[j]

    if j == len(s2):
        return i - j
    else:
        return -1

复杂度

完整代码链接