Electronic Joint Business

Solution for E-Business

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

从前面两节的介绍,我们看到不管是 暴力字符查找 还是 Rabin-Karp 字符查找都不是太有效率。为了改进算法,我们首先需要详细了解其原理。我们已经知道暴力字符匹配很慢,之后我们 Rabin-Karp 算法中在引入了哈希函数来试图改进它。问题是 Rabin-Karp 和暴力字符查找的复杂度是一样的,都是 O(mn)。 很显然,我们需要一种不同的方法,但在了解不同的方法之前,让我们看看暴力字符串搜索的问题出在什么地方。在仔细了解其原理之后,我们可以回答这个问题。 在暴力匹配中,我们将文本的每一个字符和模式字串的第一个字符相比较。在匹配的情况下,我们转而比较模式的第二个字符和文本的下一个字符…。问题是,一旦这时发生不匹配的情况,就需要在文本中回溯多个位置。因此这种技术无法被优化。 如上图所示,一旦有个字符不匹配,我们必须回溯,从一个已经查找过的位置重新开始比较。在例子中,我们比较了文本和模式的第一,第二,第三个字符,在第四个字符出现了不匹配,然后……我们回溯回文本的第二字母开始重新比较。比如 在 “abcdefg” 中搜索 “abcdeg”,前五个字符 “abcdeg” 都是匹配的,第六个字符 f 和 g 不匹配,这时候,对于暴力搜索算法,i 将会+1,整个匹配重新开始一次,这就是回溯了。 仔细想一下,回溯其实完全可以避免的,因为如果知道是在第六个字符不匹配,那就说明前五个字符都是匹配的,对于这个例子来说,我们肯定知道源字符串前面五个字符是”abcde”。 概述 解决这个问题的方法是 James H. Morri 和 Vaughan Pratt 在1977年提出的算法,通过省略大量无用的比较,该算法获得了比暴力字符串匹配高得多的效率。通过预先计算模式字符串中相应字符处的回溯索引,避免了模式匹配时不必要的回溯操作,从而提高了效率,将时间复杂度变成了O(m+n)。如下图所示: 为此我们先要对模式进行预处理以获得下一个匹配的可能位置。当开始查找一个可能的匹配时,遇到不匹配的情况,我们知道我们可以跳转到何处以省略不需要的比较。 KMP 搜索的实例说明 为了详细说明该算法,我们通过一个例子来了解算法是如何工作的。在运行的时候,该算法利用两个整数 m 和 i 来界定运算的边界,其中 m 表示目标字符串 S 正在和 W 做匹配的位置,i 则表示模式字符串 W 里正在进行比较的位置。开始运行时的状态可以描述如下: 1       […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.