Python中的Knuth Morris Pratt算法

引言

在本教程中，我们将学习Python中的Knuth Morris Pratt算法。Knuth Morris Pratt算法也称为KMP。当我们为序列模式创建LPS序列时，KMP将类似于简单的模式搜索。唯一的区别是，KMP使用LPS在发生冲突的同一位置继续，而不是在文本中前进一个字符并从字符串模式的开头开始。现在，我们给定文本txt[0..n-1]和模式pat[0..m-1]，然后编写函数search(char pat[], char txt[])来打印pat[]在txt[]中的所有出现。您可以假设n > m。

示例

现在，我们给出Knuth Morris Pratt或KMP算法在Python中的一些输入示例及其对应的输出。示例如下——

程序代码

模式搜索是计算机科学中的一个重要主题。当我们在记事本或Word文件、浏览器或数据库中搜索字符串时，会使用标准的搜索算法来显示搜索结果。所以，现在我们给出一个Python中Knuth Morris Pratt或KMP算法的例子。代码如下——

输出

现在，我们在 Python 中编译上述代码，成功编译后运行它。输出如下：

The pattern is found at index:  0
The pattern is found at index:  9
The pattern is found at index:  12

The pattern is found at index:  28

The pattern is found at index:  6

朴素字符串匹配算法的缺点是该算法运行速度非常慢。这意味着该算法的时间复杂度非常高。为了解决这个问题，我们可以使用KMP字符串匹配算法。它将字符串匹配算法的时间复杂度提高到O(n)，即线性时间。