Electronic Joint Business

Solution for E-Business

kmp

字符串查找算法 (三) Morris-Pratt 查找算法 (KMP)

从前面两节的介绍,我们看到不管是 暴力字符查找 还是 Rabin-Karp 字符查找都不是太有效率。为了改进算法,我们首先需要详细了解其原理。我们已经知道暴力字符匹配很慢,之后我们 Rabin-Karp 算法中在引入了哈希函数来试图改进它。问题是 Rabin-Karp 和暴力字符查找的复杂度是一样的,都是 O(mn)。

很显然,我们需要一种不同的方法,但在了解不同的方法之前,让我们看看暴力字符串搜索的问题出在什么地方。在仔细了解其原理之后,我们可以回答这个问题。

在暴力匹配中,我们将文本的每一个字符和模式字串的第一个字符相比较。在匹配的情况下,我们转而比较模式的第二个字符和文本的下一个字符…。问题是,一旦这时发生不匹配的情况,就需要在文本中回溯多个位置。因此这种技术无法被优化。

如上图所示,一旦有个字符不匹配,我们必须回溯,从一个已经查找过的位置重新开始比较。在例子中,我们比较了文本和模式的第一,第二,第三个字符,在第四个字符出现了不匹配,然后……我们回溯回文本的第二字母开始重新比较。比如 在 “abcdefg” 中搜索 “abcdeg”,前五个字符 “abcdeg” 都是匹配的,第六个字符 f 和 g 不匹配,这时候,对于暴力搜索算法,i 将会+1,整个匹配重新开始一次,这就是回溯了。

仔细想一下,回溯其实完全可以避免的,因为如果知道是在第六个字符不匹配,那就说明前五个字符都是匹配的,对于这个例子来说,我们肯定知道源字符串前面五个字符是”abcde”。

>>> 阅读全文