kmp 算法

KMP 算法

在计算机科学中，克努斯-莫里斯-普拉特字符串查找算法（英语：Knuth–Morris–Pratt algorithm，简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。

这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。

原理

该算法不像其他算法那样逐个匹配，它会在一个数组中存储一些历史匹配（我们通常称之为 next ）以减少遍历次数。

例如，如果我们给定一个要匹配的字符串 ABAABABCAA ，以及字符字符串 ABABC ，那么我们如何得到第一个匹配的位置？

当然，你可以立即给出答案 3 （匹配位置从零开始），这是你的大脑告诉你的。

那么我们如何让计算机来做呢？

让我们仔细看看这些字符串，当我们匹配部分字符串时，例如 ABA ，然后下一个字符是 ABAABABCAA 中的 A 。我们不会匹配成功，那么我们将如何减少比较次数。

注意 ABA ，前缀字符串和后缀字符串中包含的最长相同字符串是 A ，这意味着什么？

简单来说，当我们匹配失败时，我们不需要从头开始匹配字符串，我们可以从第二个字符 B 开始匹配，因为后缀字符串和前缀字符串有相同的字符串 A ，这意味着我们可以跳过一个字符继续比较。

在比较中， ABAABABCAA （要比较的字符串）的指针不会回退，因此我们可以在一次遍历中得到结果。

因此，我们可以很轻松的看出来，kmp 的精髓不是在于这个比较便利，而是让我们存储信息的 next 数组

现在，我们来构建一个名为 next 的数组来存储在匹配错误时可以跳过比较的字符串长度。

在我们的脑海中，逻辑只是获取前缀字符串和后缀字符串中包含的最长相同字符串，但在计算机中我们需要改变我们的思维方式。

我们可以只获取一个指向字符串 ABABC 当前位置的指针，以及另一个表示前缀和后缀最长长度的数字变量。对于第一个字符 A ，我们需要在 next 数组中存储 0 ，然后 AB ，前缀和后缀中不存在相同字符串，因此存储 0 ，当 ABA 时，第一个字符 A 和第三个字符 A 是相同的，因此我们可以在第三个元素中存储 1 。

这实际上就是一个 next 数组生成的过程，但这仅仅是人脑所想，我们需要用计算机语言将它表示出来！

next 数组

next[i] 表示模式字符串 P 的前缀 P[0...i-1] 中，最长的相等前后缀的长度。

前后缀的定义是：

前缀：字符串的开头部分，不包括整个字符串。

后缀：字符串的结尾部分，不包括整个字符串。

• 构建数组

  初始化：

  创建一个长度为模式字符串长度的 next 数组，初始值为 0 。

  设置两个指针： i 用于遍历模式字符串，从 1 开始； j 用于记录前缀的长度，从 0 开始。

  遍历模式字符串：

  当 P[i] 和 P[j] 相等时，说明找到了一个更长的前后缀： 更新 next[i] = j + 1 ，表示当前字符的最长前后缀长度。 同时将 j 增加 1 ， i 增加 1 ，继续比较下一个字符。 当 P[i] 和 P[j] 不相等时： 如果 j 不为 0 ，说明可以通过 next 数组回溯，更新 j 为 next[j-1] ，继续比较。 如果 j 为 0 ，说明没有相等的前后缀，设置 next[i] = 0 ，并将 i 增加 1 。

代码实现

以下是使用 python 代码实现的效果：

def compute_next(pattern):
    m = len(pattern)
    next = [0] * m  # 初始化 next 数组
    j = 0  # j 是前缀的长度
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:  # 当不相等时
            j = next[j - 1]  # 回溯到上一个最长前后缀
        if pattern[i] == pattern[j]:  # 当相等时
            j += 1  # 增加前缀长度
        next[i] = j  # 更新 next[i]
    return next

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    next = compute_next(pattern)  # 计算 next 数组
    j = 0  # 模式字符串的指针

    for i in range(n):  # 遍历文本字符串
        while j > 0 and text[i] != pattern[j]:  # 当不匹配时
            j = next[j - 1]  # 回溯
        if text[i] == pattern[j]:  # 当匹配时
            j += 1  # 增加模式字符串的指针
        if j == m:  # 找到匹配
            print(f"模式字符串 '{pattern}' 在文本中出现，起始位置: {i - m + 1}")
            j = next[j - 1]  # 继续查找下一个匹配

# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
kmp_search(text, pattern)