C++ KMP 算法

在本教程中，我们将通过代码实现来学习 C++ 中的 KMP 算法。其他用于模式匹配的算法包括朴素算法和 Rabin Karp 算法。如果我们比较这些算法，朴素方法和 Rabin Karp 的时间复杂度为 O((n-m)*m)；然而，Rabin Karp 通常优于朴素方法。另一方面，KMP 算法的时间复杂度为 O(n)，附加空间为 O(m)。在此示例中，模式字符串和文本字符串的长度分别为 m 和 n。

朴素的模式匹配方法，其中 n 是文本长度，m 是模式长度，如所示，运行时间为 O(n.m)。这是因为该算法缺乏对先前匹配字符的记忆。本质上，它反复将一个字符与一个不同的模式字符进行匹配。

KMP 方法（或 Knuth, Morris, 和 Pratt 字符串搜索方法）之所以有效，在于巧妙地利用了先前的比较数据。由于它从不再次比较已经匹配过模式符号的文本符号，因此它可以在 O(n) 时间内找到模式。为了检查模式结构，它使用一个部分匹配表。构建部分匹配表需要 O(m) 时间。因此，KMP 算法的总时间复杂度为 O(m + n)。

编写一个函数 search(char pat[], char txt[])，该函数在给定文本 txt[0... N-1] 和模式 pat[0... M-1] 时，输出 pat[] 在 txt[] 中的所有实例。N > M 是一个合理的假设。

示例

输出

在索引 0 处检测到一个模式，然后在索引 9 和索引 12 处检测到模式。

模式搜索是计算机科学中的一个重要问题。当我们对数据库、浏览器或记事本/文字文件执行字符串搜索时，模式搜索方法会显示搜索结果。

在上一个帖子中，我们讨论了朴素模式搜索算法。朴素算法的最坏情况复杂度为 O(m(n-m+1))。KMP 算法的最坏情况时间复杂度为 O(n+m)。

使用 KMP (Knuth Morris Pratt) 进行模式搜索

当多个匹配字符后跟一个不匹配字符时，朴素模式搜索算法在查找模式时会遇到困难。

例如，

1. txt[] = "AAAAAAAAAAAAAB"，2) pat[] = "AAAAB"。
2. pat[] = "ABABAC"，txt[] = "ABABABCABABABCABABABC"（不是最坏情况，但对朴素算法来说很糟糕）

KMP 匹配算法利用模式的退化特性，当相同的子模式在模式中出现不止一次时，将最坏情况复杂度降低到 O(n+m)。

KMP 方法的基本原则是，如果我们看到一个差异（在几次匹配之后），我们就已经知道下一个窗口文本中的一些字符。利用这些知识，我们可以避免匹配我们知道会匹配的字符。

文本 "AAAAABAAABA." 的比较概述。

Pat 是 "AAAA"

我们比较第一个文本窗口和 pat。

pat = "AAAA" 和 txt = "AAAAABAAABA" [起始位置]

我们找到了一个匹配。这与朴素字符串匹配类似。

接下来，我们将文本文件的下一个窗口与 pat 进行比较。

文本 "AAAAABAAABA"

pat 等于 "AAAA" [模式移位一位]

KMP 在这种情况下对朴素算法进行了优化。为了确定当前文本窗口是否与模式匹配，我们只需将模式的第四个 A 与第二个窗口中的第四个字母进行比较。我们省略了前三个字符的匹配，因为我们知道它们会匹配。

需要预处理吗？

如前所述，解释提出了一个关键问题：我如何确定要跳过多少个字符？我们预处理模式以确定这一点，并创建一个名为 lps[] 的整数数组，其中包含将要跳过的字符数。

预处理概述

为了在匹配时跳过字符，KMP 算法会对模式进行预处理，并创建一个大小为 m（与模式大小相同）的辅助 lps 数组。

最长的匹配前缀也是后缀，由名称 lps 表示。合适的前缀包含一个完全禁止的字符串。例如，“ABC”的前缀包括“”、“A”、“AB”和“ABC”。合适的前缀是“”、“A”和“AB”。字符串有后缀“”、“C”、“BC”和“ABC”。

• 我们寻找包含 lps 的子模式。我们更具体地关注用作前缀和后缀的模式的子字符串。
• 对于每个子模式 pat[0..i]，其中 i = 0 到 m-1，lps[i] 存储了 pat[0..i] 的最长匹配的有效前缀，该前缀也是 pat[0..i] 的后缀。

lps[i] 是 pat[0..i] 的最长有效前缀，也是 pat[0..i] 的后缀。

应该注意的是，lps[i] 也是最长的前缀，它是有效的后缀。我们必须在一个位置恰当地使用它，以确保整个子字符串不会被考虑在内。

lps[] 构建示例

模式 "AAAA" 的 lps[] 值为 [0, 1, 2, 3]。

模式 "ABCDE" 的 lps[] 值为 [0, 0, 0, 0, 0]。

模式 "AABAACAABAA" 的 Lps[] 是 [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]。

模式 "AAACAAAAAC" 的 lps[] 值为 [0, 1, 2, 0, 1, 2, 3, 3, 4, 5]。

模式 "AAABAAA" 的 lps[] 值为 [0, 1, 2, 0, 1, 2, 3]。

预处理算法

在此阶段，我们计算 lps[] 中的值。为了做到这一点，我们使用 len 变量来跟踪前一个索引的最长前缀后缀值长度。

• 我们将 lps[0] 和 len 设置为零。
• 如果 pat[len] 和 pat[i] 相等，则 len 增加 1，并将结果值赋给 lps[i]。
• 如果 len 不为 0 且 pat[i] 和 pat[len] 不相等，我们将 len 更新为 lps[len-1]。
• 有关更多信息，请参阅下面的代码中的 computeLPSArray()。

预处理（或 lps[] 创建）示例

len = 0, i = 0, pat[] = "AAACAAAA"

• 由于 lps[0] 始终为 0 且 i = 1 之后 len = 0，i = 1
• 由于 pat[len] 和 pat[i] 匹配，执行 len++，将其保存在 lps[i] 中，然后执行 i++。
• 如果 len = 1 且 lps[1] = 1，则 len = 1 且 i = 2 获得
• 由于 pat[len] 和 pat[i] 匹配，执行 len++，将其保存在 lps[i] 中，然后执行 i++。
• 如果 len = 2 且 lps[2] = 2 且 i = 3，则 len = 2 且 i = 3
• 由于 len > 0 且 pat[len] 和 pat[i] 不兼容，
• 使 len 等于 lps[len-1] = lps[1] = 1。
  • len = 1, i = 3
• 由于 len > 0 且 pat[len] 和 pat[i] 不匹配，len = lps[len-1] = lps[0] = 0，因此 len = 0, i = 3
• 鉴于 len = 0 且 pat[len] 和 pat[i] 不相等，将 lps[3] 设置为 0 并将 i 设置为 4 以获得 len = 0, i = 4
• 由于 pat[len] 和 pat[i] 匹配，执行 len++，将其保存在 lps[i] 中，然后执行 i++。
• 如果 len = 1 且 lps[4] = 1，则 i = 5 且 len = 1
• 由于 pat[len] 和 pat[i] 匹配，执行 len++，将其保存在 lps[i] 中，然后执行 i++。
• 将 len 设置为 2，lps[5] 设置为 2，i 设置为 6。
• 如果 len = 2 且 i = 6，执行以下步骤：执行 len++，将结果保存在 lps[i] 中，然后执行 i++。
• Len = 3, lps[6] = 3, and i = 7 such that Len = 3, i = 7
• 由于 len > 0 且 pat[len] 和 pat[i] 不相等，
• 如果 len = lps[len-1] = lps[2] = 2，则 i = 7 且 len = 2
• 由于 pat[len] 和 pat[i] 匹配，执行 len++，将其保存在 lps[i] 中，然后执行 i++。
• Len = 3, lps [7] = 3, and i = 8
• 由于整个 LP 已构建完成，我们在此结束。

KMP 算法实现

与朴素方法不同，朴素方法是在每次移位时滑动模式一位并比较所有字符，而我们则利用 lps[] 中的值来确定下一步必须匹配哪些字符。目标是避免匹配一个可能匹配的字符。

如何使用 lps[] 选择下一个位置（或确定需要跳过多少个字符）？

• 我们开始比较当前活动文本窗口的 pat[j] 字符，其中 j = 0。
• 只要 pat[j] 和 txt[i] 匹配，我们就继续匹配 txt[i] 和 pat[j] 字符，并递增 i 和 j。
• 当我们注意到不匹配时，字符 pat[0..j-1] 匹配字符 txt[i-j...i-1]。 （请记住，j 仅在匹配时增加其值，否则从 0 开始）。
• 根据上面的定义，我们还知道 lps[j-1] 是 pat[0...j-1] 中既是有效前缀又是真后缀的字符数。
• 从前面提到的两个考虑因素，我们可以推断出，我们不需要将这些 lps[j-1] 字符与 txt[i-j...i-1] 进行匹配，因为我们知道它们会匹配。让我们以先前提到的示例来进一步理解这一点。

上述方法如下所示

考虑 txt = "AAAAABAAABA", pat = "AAAA"

如果使用上述 LPS 构建过程，则 lps[] = 0, 1, 2, 3 -> i = 0, j = 0: txt[i] 和 pat[j] 匹配，执行 i++, j++ -> i = 1, j = 1: txt[i] 和 pat[j] 匹配，执行 i++, j++ -> i = 3, j = 3: txt[i] 和 pat j = lps[j-1] = lps[3] = 3，因为 j = M，打印模式已被发现，j 被重置。

与朴素算法相比，我们在这里不匹配此窗口的前三个字符。在上一阶段，lps[j-1] 的值提供了下一个要匹配的字符的索引。

• i = 4, j = 3: 当 txt[i] 和 pat[j] 匹配时，执行 i++, j++。
• i = 5, j = 4: 由于 j == M，打印的模式被检测到并重置为 j，然后等于 lps[j-1] + lps[3] = 3。
• 与朴素方法相比，我们再次不匹配此窗口的前三个字符。在上一阶段，lps[j-1] 的值提供了下一个要匹配的字符的索引。
  • i = 5, j = 3: txt[i] 和 pat[j] 不相等，且 j > 0；只需更改 j。j = lps[j-1] = lps[2] = 2。
  • 当 i = 5, j = 2 且 txt[i] 和 pat[j] 不匹配时，j = lps[j-1] = lps[1] = 1。
  • 当 i = 5 且 j = 1 且 txt[i] 和 pat[j] 不匹配时，j = lps[j-1] = lps[0] = 0。
  • i = 5, j = 0: 由于 j 为 0 且 txt[i] 和 pat[j] 不匹配，我们执行 i++。
  • 如果 i = 6 且 j = 0，则必须执行 i++ 和 j++。
  • 如果 i = 7 且 j = 1，则必须执行 i++ 和 j++。

此过程将持续进行，直到文本中有足够的字符可以与模式中的字符进行比较。

正如前面提到的，该策略的应用如下所示

C++ KMP 模式搜索实现

输出

Found pattern at index 10

说明

在上面的代码中，我们使用了 C++ 编程语言的 KMP 算法。KMP 算法用于模式匹配。因此，我们从给定的输入中找到了索引 10 处的模式，如输出所示。

时间复杂度

O(N+M)，其中 N 是文本长度，M 是需要发现的模式长度。

辅助空间

O(M)