字符串朴素匹配算法和KMP算法

2020-05-25 本文已影响0人爱吃鱼的夏侯莲子

字符串的匹配在平常的编码过程中非常常用，在编程语言中通常是调用一个内置函数就可以实现字符串的匹配，当不让使用内置的函数，而是自己编写一个函数来实现匹配的功能，应该如何来写呢？

今天介绍两个算法，朴素匹配算法，和无回溯匹配算法中的KMP算法。

朴素匹配算法

朴素匹配算法就是按照常识来，最容易理解的逐个字符匹配。
从待匹配字符串中的某个下标i开始，匹配字符串从0开始，逐个匹配。当有不匹配的字符时，重新从i+1下标开始重复上次的匹配过程。

图(1) 朴素匹配算法

下面用代码实现一下：
t表示待匹配字符串，p表示用来匹配的字符串。

$p_i$ 表示p字符串的第i个下标的字符。

def naive_match(t, p):
    """
    t 目标字符串
    p 匹配字符串
    """
    m, n = len(p), len(t)
    i, j = 0, 0
    while i < m and j < n:
        if p[i] == t[j]: # 字符相同，考虑下一字符
            i, j = i + 1, j + 1
        else:
            i, j = 0, j - i + 1  # 字符不同，查找字符串重置，目标字符串回溯

    if i == m:
        return j - i
    return -1

朴素匹配算法非常简单，容易理解。当然，它的效率也是很低的，造成效率低的原因是在执行过程中会有回溯。当遇到p[i] != t[j]时，匹配字符串下标置0，待匹配字符串的下标回到上一次检查的下一个位置，往回退了j - i + 1个位置。

这种操作造成的效率很低。最坏的情况是，每次匹配都是到最后一个字符的时候不匹配。例如：
待匹配字符串： 0000000000001
匹配字符串： 00001
这样需要 n-m+1次比较，总的比较次数就是(n-m+1) * m，这样它的复杂度就是：O(n*m)

KMP算法

朴素算法的效率低，根源上是把每次匹配都看成的单独的事件，没有利用到之前的匹配信息。而其他改进算法就是利用了之前的匹配信息。

KMP算法的基本思想就是在匹配中不回溯。

图(2) KMP算法图解

描述KMP算法，需要借助上图。
待匹配字符串t，和匹配字符串p。
在匹配过程中，p的第i个字符在和t的第j个字符比较，这时， $t_{j-i}$ ～ $t_{j-1}$ 和 $p_0$ ～ $p_{i-1}$ 相等，匹配完成。下面要做的步骤可以分为两个：

当 $t_j = p_i$ 时，继续进行下一个字符的比较。
当 $t_j \neq p_i$ 时，这是不需要重置p，而是找到一个位置k( $0\leq k < i$ )，使得 $t_{j-k}$ ～ $t_{j-1}$ 等于 $p_0$ ～ $p_{k-1}$ ，继续匹配 $t_{j}$ 和 $p_{k}$ ，重复上面的步骤。这样待匹配字符串也不需要回溯到前面去重新匹配。

KMP算法中的关键认识是：在 $p_i$ 匹配失败时，所有的 $p_k$ ( $0\leq k < i$ )都已经匹配成功。也就是说，待匹配字符串中的 $t_j$ 之前的i个字符，与匹配字符串中的前i个字符 $p_0,p_1,...,p_{i-1}$ 。
通过上面的分析，要找到k，完全可以先不管待匹配字符串，而是研究一下匹配字符串p，通过p找到它前移的位置k。

得出一个结论：在p中，其中的每一个字符的i都会有其对应的下标k，与待匹配的字符串无关。

因此，我们可以为匹配字符串设计一个列表来存储每一个i的下标k。假设p的长度为m，用一个长度为m的列表pnext来存储，用表元素pnext[i]来表示i个元素的下标k值。
有一种特殊情况： $p_i$ 匹配失败后，之前所做的匹配都没有用，需要从头开始匹配，用 $p_0$ 与 $t_{j+1}$ 比较。在这种特殊情况下可以在pnext[i]中存入-1来表示。显然， $p_0$ 一直为-1。

KMP主算法

当假设pnext已经获得了，KMP的算法实现为：

def kmp_match(t, p, pnext):
    """
    KMP匹配，主函数
    """
    i, j = 0, 0
    m, n = len(p), len(t)
    while i < m and j < n:
        if i == -1: # -1 匹配下一队字符
            i, j = i + 1, j + 1
        elif p[i] == t[j]: # 相等，匹配下一对字符
            i, j = i + 1, j + 1
        else:
            i = pnext[i] # 从pnext中拿出下一个字符应该的位置

    if i == m:
        return j - i
    return -1

该算法的时间复杂度为O(n)，因为j的循环次数不会超过n，i = pnext[i]的次数不会超过m。

pnext的实现

最长相等前后缀

已知pnext[0]=-1，并且pnext[0]到pnext[i-1]已知的情况下，求解pnext[i]:

假设pnext[i-1]=k-1，如果 $p_i=p_k$ ，则 $p_0,p_1,...,p_i$ 的最长的匹配相等长度为k，记下pnext[i]=k。
如果 $p_i \neq p_k$ ，就将k的值设为pnext[k]，即考虑前一个保证匹配的字符串，且更短。
假如k的值为-1（由第二步造成，一直到不到可以匹配的字符串），那么就将pnext[i]设置为0，将i递增后继续检查。

构造方法如下：

def gen_pnext(p):
    i, k, m = 0, -1, len(p)

    pnext = [-1] * m

    while i < m - 1:
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            pnext[i] = k
        else:
            k = pnext[k]

    return pnext

举例：匹配字符串为 abbcabcaabbcaa，得到的pnext为：
[-1, 0, 0, 0, 0, 1, 2, 0, 1, 1, 2, 3, 4, 5]

pnext生成算法的改进

在pnext的生成中，对pnext[i]的设置可以有些优化。
在图(2)中， $p_i \neq t_j$ 匹配失败，假设pnext[i]=k，如果发现 $p_i=p_k$ ，那么也一定有 $p_k \neq t_j$ ，所以，这种情况下pnext[i]的位置移动到pnext[k]，这一修改减少了一个比较步骤，有可能提高效率。修改后：

def gen_pnext(p):
    i, k, m = 0, -1, len(p)

    pnext = [-1] * m

    while i < m - 1:
        if k == -1 or p[i] == p[k]:
            i, k = i + 1, k + 1
            if p[i] == p[k]:
                pnext[i] = pnext[k]
            else:
                pnext[i] = k
        else:
            k = pnext[k]

    return pnext

举例：匹配字符串为 abbcabcaabbcaa，得到的pnext为：
[-1, 0, 0, 0, -1, 0, 2, -1, 1, 0, 0, 0, -1, 5]

pnext的复杂度为O(m)，所以整个KMP算法的复杂度O(m+n)，由于m小于n，可以认为复杂度为O(n)，优于朴素算法。

转载自：
https://codeeper.com/2020/05/23/tech/python/structure/str-search-and-kmp.html