Knuth-Morris-Pratt(KMP) 算法简介

Created: November-22, 2018

假设我们有一个文本和一个模式。我们需要确定文本中是否存在模式。例如：

+-------+---+---+---+---+---+---+---+---+
| `Index` | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+-------+---+---+---+---+---+---+---+---+
|  Text | a | b | c | b | c | g | l | x |
+-------+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+
| `Index`   | 0 | 1 | 2 | 3 |
+---------+---+---+---+---+
| `Pattern` | b | c | g | l |
+---------+---+---+---+---+

这种模式确实存在于文本中。所以我们的子字符串搜索应该返回 3 ，即该模式开始的位置的索引。那么我们的强力子搜索程序如何工作呢？

我们通常做的是：我们从一开始第 0 中的索引文本和第 0 我们*模式的指数，我们比较文本[0] 与图案[0] 。由于它们不匹配，我们转到文本的下一个索引，我们将 Text [1] 与 Pattern [0]进行比较。由于这是匹配，我们也增加模式的索引和文本的索引。我们将 Text [2] 与 Pattern [1]进行比较。他们也是一个匹配。按照之前说明的相同程序，我们现在将 Text [3] 与 Pattern [2]进行比较。由于它们不匹配，我们从下一个开始寻找匹配的位置开始。这是指数 2 中的文本。我们将 Text [2] 与 Pattern [0]进行比较。他们不匹配。然后递增 Text 的索引，我们将 Text [3] 与 Pattern [0]进行比较。他们相配。再次 Text [4] 和 Pattern [1] 匹配， Text [5] 和 Pattern [2] 匹配， Text [6] 和 Pattern [3] 匹配。由于我们已经到达模式的末尾，我们现在返回匹配开始的索引，即 3 。如果我们的模式是：bcgll，这意味着如果我们的文本中不存在模式，我们的搜索应该返回异常或 -1 或任何其他预定义的值。我们可以清楚地看到，在最坏的情况下，这种算法将采取 O(mn) 时间，其中米是长度的文本和 ñ 是的长度模式。我们如何减少这种时间复杂性？这就是 KMP 子字符串搜索算法进入图片的地方。 ** **** **** ** **

该克努特莫里斯普拉特的字符串搜索算法或 KMP 算法采用的是，当不匹配时，这个词本身就体现了足够的信息，以确定下一个匹配就可以开始观察搜索主文本中的模式的出现因此绕过了对先前匹配的字符的重新检查。该算法由 Donuld Knuth和 Vaughan Pratt于 1970 年构思，由 James H. Morris独立构思。三人于 1977 年联合出版。

让我们扩展我们的示例 Text 和 Pattern 以便更好地理解：

+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| `Index` |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 |10|11|12|13|14|15|16|17|18|19|20|21|22|
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  Text |a |b |c |x |a |b |c |d |a |b |x |a |b |c |d |a |b |c |d |a |b |c |y |
+-------+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | y |
+---------+---+---+---+---+---+---+---+---+

首先，我们的文本和模式匹配到索引 2 。文本[3] 和模式[3] 不匹配。所以我们的目标是不要在本文中倒退，也就是说，如果不匹配，我们不希望我们的匹配从我们开始匹配的位置再次开始。为了实现这一点，我们将在我们的不匹配发生之前在我们的模式中寻找一个后缀（substring abc ），它也是我们模式的子字符串的前缀 ** **** **** ** 。对于我们的示例，由于所有字符都是唯一的，因此没有后缀，即匹配的子字符串的前缀。那意味着什么，我们的下一个比较将从索引 0 开始。坚持一下，你会理解为什么我们这样做。接下来，我们将 Text [3] 与 Pattern [0]进行比较，但它不匹配。之后，对于从索引 4 到索引 9 的 Text 以及从索引 0 到索引 5 的 Pattern ，我们找到匹配。我们发现 Text [10] 和 Pattern [6]中存在不匹配。所以我们从 Pattern 获取子字符串 **** **** ** **** **** **** **** ** 在发生不匹配的点之前（substring abcdabc ），我们检查后缀，这也是该子字符串的前缀。我们可以看到这里 ab 是这个子字符串的后缀和前缀。这意味着，因为我们匹配到文本[10] ，不匹配之前的字符是 ab 。我们可以从中推断出，因为 ab 也是我们所采用的子字符串的前缀，所以我们不必再次检查 ab ，下一次检查可以从 Text [10] 和 Pattern [2]开始。我们没有回头看整个文本，我们可以直接从我们的不匹配发生的地方开始。现在我们检查文本[10] 和模式[2] ，因为它不匹配，并且不匹配前的子字符串（ abc ）不包含后缀也是前缀，我们检查 Text [10] 和 Pattern [0] ，它们不要’匹配。之后，对于文本从索引 11 到索引 17 和用于模式从索引 0 至索引 6 。我们在 Text [18] 和 Pattern [7]中发现不匹配。所以我们再次检查不匹配之前的子字符串（substring abcdabc ），并且发现 abc 既是后缀又是前缀。因为我们匹配到了模式[7] ， abc 必须在 Text [18] 之前。这意味着，我们不需要比较文本[17] ，我们的比较将从文本[18] 和模式[3]开始。因此我们将找到一个匹配，我们将返回 15 ，这是我们的匹配的起始索引。这就是我们的 KMP 子字符串搜索如何使用后缀和前缀信息。

现在，我们如何有效地计算 if 后缀是否与前缀相同以及在什么时候开始检查 Text 和 Pattern 之间是否存在不匹配的字符。我们来看一个例子：

+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

我们将生成一个包含所需信息的数组。让我们把数组S。数组的大小将与模式的长度相同。由于 Pattern 的第一个字母不能是任何前缀的后缀，我们将 S [0] = 0 。我们首先采用 i = 1 和 j = 0 。在每一步，我们比较 Pattern [i] 和 Pattern [j] 并增加 i 。如果匹配，我们将 S [i] = j + 1 并增加 j ，如果存在不匹配，我们检查 j 的前一个值位置（如果可用）并设置 j = S [j-1] （如果 j 不等于 0 ），我们一直这样做，直到 S [j] 没有’ t 与 S [i] 匹配或 j 不变为 0 。对于后者，我们把 S [i] = 0 。对于我们的例子：

            j   i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+

模式[j] 和模式[i] 不匹配，所以我们递增 i ，因为 j 是 0 ，我们不检查前一个值并将 Pattern [i] = 0 。如果我们继续增加 i ，对于 i = 4 ，我们将获得匹配，因此我们将 S [i] = S [4] = j + 1 = 0 + 1 = 1 并且增加 j 和 i 。我们的数组看起来像：

                j               i
+---------+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
+---------+---+---+---+---+---+---+---+---+
| `Pattern` | a | b | c | d | a | b | c | a |
+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 |   |   |   |
+---------+---+---+---+---+---+---+---+---+

由于 Pattern [1] 和 Pattern [5] 是匹配，我们把 S [i] = S [5] = j + 1 = 1 + 1 = 2 。如果我们继续，我们会发现 j = 3 和 i = 7 不匹配。由于 j 不等于 0 ，我们把 j = S [j-1] 。我们将比较 i 和 j 上的字符是否相同，因为它们是相同的，我们将把 S [i] = j + 1.我们完成的数组将如下所示：

+---------+---+---+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 1 |
+---------+---+---+---+---+---+---+---+---+

这是我们需要的数组。这里 S [i] 的非零值意味着有一个 S [i] 长度后缀与该子字符串中的前缀相同（子字符串从 0 到 i ），下一个比较将从 S [i] + 1 位置开始。模式。我们生成数组的算法如下：

Procedure GenerateSuffixArray(Pattern):
i := 1
j := 0
n := Pattern.length
while i is less than n
    if Pattern[i] is equal to Pattern[j]
        S[i] := j + 1
        j := j + 1
        i := i + 1
    else
        if j is not equal to 0
            j := S[j-1]
        else
            S[i] := 0
            i := i + 1
        end if
    end if
end while

构建这个数组的时间复杂度是 O(n)，空间复杂度也是 O(n)。为了确保你是否已完全理解该算法，请尝试为模式 aabaabaa 生成一个数组，并检查结果是否与此匹配。

现在让我们使用以下示例进行子字符串搜索：

+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |10 |11 |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+
|   Text  | a | b | x | a | b | c | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+---+---+---+---+---+---+

+---------+---+---+---+---+---+---+
|  Index  | 0 | 1 | 2 | 3 | 4 | 5 |
+---------+---+---+---+---+---+---+
| `Pattern` | a | b | c | a | b | y |
+---------+---+---+---+---+---+---+
|    S    | 0 | 0 | 0 | 1 | 2 | 0 |
+---------+---+---+---+---+---+---+

我们使用之前定义的逻辑有一个 Text ，一个 Pattern 和一个预先计算的数组 S. 我们比较 Text [0] 和 Pattern [0] ，它们是相同的。文本[1] 和模式[1] 是相同的。文本[2] 和模式[2] 不相同。我们检查不匹配之前的位置的值。由于 S [1] 为 0 ，因此没有后缀与我们的子字符串中的前缀相同，我们的比较从位置 S [1]开始，即 0 。因此 Pattern [0] 与 Text [2]不同所以我们继续前进。文本[3] 与模式[0] 相同，并且匹配到文本[8] 和模式[5] 。我们在 S 阵列中退后一步，找到 2 。所以这意味着有一个长度为 2 的前缀，它也是这个子字符串（ abcab） 的后缀，即 ab 。这也意味着在 Text [8] 之前有一个 ab 。因此我们可以安全地忽略 Pattern [0] 和 Pattern [1] 并从 Pattern [2] 和 Text [8] 开始我们的下一次比较。如果我们继续，我们会找到 **** **** **** **** **** 模式的文本。我们的程序如下：

Procedure KMP(Text, Pattern)
GenerateSuffixArray(Pattern)
m := Text.Length
n := Pattern.Length
i := 0
j := 0
while i is less than m
    if Pattern[j] is equal to Text[i]
        j := j + 1
        i := i + 1
    if j is equal to n
        Return (j-i)
    else if i < m and Pattern[j] is not equal t Text[i]
        if j is not equal to 0
            j = S[j-1]
        else
            i := i + 1
        end if
    end if
end while
Return -1

除了后缀数组计算之外，该算法的时间复杂度是 O(m)。由于 GenerateSuffixArray 采用 O(n)，因此 KMP 算法的总时间复杂度为：O(m+n)。

PS：如果要在文本中找到多次出现的 Pattern ，而不是返回值，请将其打印/存储并设置 j := S[j-1]。还要保留一个 flag 来跟踪你是否发现了任何事件，并相应地处理它。 **