KMP 算法 - 使用 Python 实现 KMP 算法

在本教程中，我们将学习使用 Python 编程语言的 KMP 算法。该算法主要用于以 O(n) 的复杂度搜索模式或子字符串。

为了测试开发者的能力，技术面试中可能会问到该算法。

KMP 算法

KMP 代表 Knuth-Morris-Prat，它是一种模式搜索算法。它用于解决字符串匹配问题。这个问题在信息安全、模式识别、文档匹配、生物信息学等领域有广泛的应用。它由 Donald-Knuth 和 Vaughan Pratt 于 1970 年通过深入分析朴素方法而开发，提出了线性时间解决方案。

部分匹配表

部分匹配表是 KMP 的关键。要理解 KMP，我们需要掌握部分匹配表的概念。在本节中，我们将用简单的语言解释部分匹配表。

让我们看下面的例子 -

如果我们有一个八个字符的模式字符串，部分匹配表将有八个单元格。如果我们使用表中的第七个单元格，这意味着我们只关心模式中的前七个字符。第八个字符（“a”）无关紧要。第六个单元格也会发生同样的情况。

现在，为了谈论其含义，我们需要了解真前缀和真后缀。让我们看看这些术语是什么。

真前缀 - 字符串中的所有字符，末尾去掉一个或多个字符。“T”、“Ti”、“Tig”、“Tige” 和 “Tiger” 都是 “Tiger” 的真前缀。

真后缀：字符串中的所有字符，开头去掉一个或多个字符。“arry”、“rry”、“rr”、“ry”和“y”都是“Harry”的真后缀。

子（模式）中最长真前缀与同一（子）模式中的真后缀匹配的长度。

让我们用一个例子来理解它。假设我们正在查看第三个单元格，这意味着我们只关心前三个字符（“aba”）。在“aba”中，有两个真前缀（“a”和“ab”）和两个真后缀（“a”和“ba”）。正如我们所见，真前缀“ab”与两个真后缀中的任何一个都不匹配。然而，真前缀“a”与真后缀“a”匹配。因此，在这种情况下，匹配的真前缀的最长长度是 1。

现在让我们检查第五个单元格，它涉及到“ababa”，它有真前缀（'a'、'ab'、'aba' 和 'abab'）和四个真后缀（'a'、'ba'、'aba' 和 'baba'）。现在我们得到了真前缀和真后缀。由于 aba 比 a 长，所以它胜出，第五个单元格的值为 3。