KMP字符串匹配算法的理解

前言

在计算机科学中, 字符串搜索是一个很常见的任务. 给定两个字符串A和B, 例如

1 2	A -> ABC ABCDAB ABCDABCDABDE B -> ABCDABD

我们怎么知道 A 是否包含有 B ?

有很多种算法可以完成这个任务, Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）是比较著名的一种.

这个算法由高德纳（Donald Knuth）和沃恩·普拉特（英语：Vaughan Pratt）在1974年构思，同年詹姆斯·H·莫里斯（英语：James H. Morris）也独立地设计出该算法，最终三人于1977年联合发表.

没错! 起头的那个 K 就是高德纳老爷子

该算法的巧妙之处在于, 一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配對的字符。（来自维基百科）

emmm….

我觉得，上面的话似乎不太好懂，我个人的理解是，该算法设计了一种方法，利用已经匹配过的信息，来减少重新匹配的次数。

以下的文章基于阮一峰的网络日志，特地记录了下学习的过程，以加强理解。

算法流程

如上图，首先字符串“BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词“ABCDABD”的第一个字符进行比较，因为B与A不匹配，所以我们将搜索词后移一位。

因为B与A不匹配，我们继续后移。

如此直到字符串有一个字符与搜索词的第一个字符匹配到为止。

接着比较字符串和搜索词的下一个字符，还是相同。

直到字符串有一个字符，与搜索词对应的字符不相同为止。

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把”搜索位置”移到已经比较过的位置，重比一遍。

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

已知空格与D不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符B对应的”部分匹配值”为2，因此按照下面的公式算出向后移动的位数

1	移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（”AB”），对应的”部分匹配值”为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

因为空格与A不匹配，继续后移一位。

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

如何计算部分匹配表

首先，要了解两个概念：”前缀”和”后缀”。 “前缀”指除了最后一个字符以外，一个字符串的全部头部组合；”后缀”指除了第一个字符以外，一个字符串的全部尾部组合。

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例，

字符串	前缀	后缀	最长共有元素	最长共有元素的长度
A	空集	空集	无	0
AB	A	B	无	0
ABC	A, AB	BC, C	无	0
ABCD	A, AB, ABC	BCD, CD, D	无	0
ABCDA	A, AB, ABC, ABCD	BCDA, CDA, DA, A	A	1
ABCDAB	A, AB, ABC, ABCD, ABCDA	BCDAB, CDAB, DAB, AB, B	AB	2
ABCDABD	A, AB, ABC, ABCD, ABCDA, ABCDAB	BCDABD, CDABD, DABD, ABD, BD, D	无	0

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDAB”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第一个”AB”向后移动4位（搜索串长度-部分匹配值），就可以来到第二个”AB”的位置。

Python 实现

from typing import List


def KMP(text: str, pattern: str, search_all: bool = True) -> List[int]:
    """KMP字符串搜索算法"""

    t_len = len(text)
    p_len = len(pattern)

    # 模式串长度小于待搜索的字符串
    if t_len < p_len:
        return []

    i = 0
    result = []
    while i < t_len:
        is_match = True
        # 匹配最后一部分时, 起始坐标加上模式串的
        # 长度大于文本长度时, 注定匹配失败, 所以
        # 不用多此一举匹配最后部分
        if i + p_len > t_len:
            break
            
        for j in range(len(pattern)):
            if text[i + j] != pattern[j]:
                # 第一位就不匹配
                if j == 0:
                    is_match = False
                    i += 1
                    break
                # 其余位不匹配时, 计算偏移值(对应的部分匹配值)
                is_match = False
                p_offset = partial_match(pattern[:j])
                # 移动位数 = 已匹配的字符数 - 偏移值(对应的部分匹配值)
                i += j - p_offset
                break

        if is_match:
            result.append(i)
            if not search_all:
                break
            i += p_len - partial_match(pattern)

    return result

def partial_match(p: str) -> int:
    """计算部分匹配值

    例如:
        in:     "ABCDAB"
        out:    2
    
    假设我们输入"ABCDAB", 则可知道该字符串的长度为 6, 最大下标(max_index)为 5

        字符:   A B C D A B
        下标:   0 1 2 3 4 5

    前缀和后缀的可选范围
    
        Prefix: 0 1 2 3 4
        Suffix:   1 2 3 4 5

    于是我们知道

        i   prefix          suffix          diffrence(前缀和后缀的差值)
        -                                   
        0   0               5               5
        1   0, 1            4, 5            4
        2   0, 1, 2         3, 4, 5         3
        3   0, 1, 2, 3      2, 3, 4, 5      2
        4   0, 1, 2, 3, 4   1, 2, 3, 4, 5   1

    我们最多需要进行 5 次循环, i 表示当前循环的次数, prefix 和 suffix 分别
    对应了该次循环时每个字符的下标, diffrence 表示了该次循环时, prefix 和
    suffix 对应的下标的差值, 显然可知

        diffrence = max_index - i

    我们需要取最长的共有元素的长度, 很显然我们从大到小搜索效率最高, 我们只需要
    搜索到一个有效值, 该值即是最优解. 对应上图即为从下往上搜索.
    """

    if len(p) == 1:
        return 0

    max_macth_length = 0
    max_index = len(p) - 1
    i = max_index - 1

    # 从大到小搜索仅需要搜索到一个即是最优值
    while i > -1:
        is_match = True
        diff = max_index - i
        for j in range(i + 1):
            if p[j] != p[j + diff]:
                is_match = False
                break
        if is_match:
            max_macth_length = i + 1
            break
        i -= 1
    return max_macth_length

测试

1
2
3

text = "ABC ABCDAB ABCDABCDABDEABCDABD"
pattern = "ABCDABD"
print(KMP(text, pattern))

输出

[15, 23]

参考链接

https://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html