KMP (Knuth Morris Pratt) Pattern Searching

KMP (Knuth Morris Pratt) Pattern Searching

模式匹配 (Pattern Searching)

解决问题:

寻找一段长字符串中的模式字符串,问题通常为求模式字符串出现次数、第一次出现模式字符串的位置等。

这里讨论的是KMP方法,这个方法对传统的简单匹配方法进行了优化。为了方便理解KMP方法的优势,先大致说明一下简单匹配方法,简单的匹配方法具有\(O(m * n)\)的复杂度,它的策略是:遍历长字符串中的每一个字符,并尝试与模式字符串的第一个字符进行匹配,如果它们相同,则开始尝试将模式字符串剩下的部分与长字符串从这个字符处开始之后的部分依次匹配,遇到不匹配的字符便中止,重新回到外层循环,继续遍历长字符串中的每一个字符;而如果刚才内层循环的匹配操作可以持续到模式字符串末尾,则说明成功找到了一个匹配字符串。

简单匹配方法十分好理解,但是缺点也十分明显,如下这个例子,假设:

模式字符串为:aaaaaac

长字符串为:acaacaaaacaaaaaacaaaaaaaaac

在诸如此类模式字符串中有很多重复模式的时候,使用简单匹配方法常常会需要遍历多次模式字符串,而我们其实是可以事先根据模式字符串中的重复模式知道,重复这样的无意义匹配是无意义的,KMP算法便是消除这种无意义匹配的一种解决方案。

对于模式字符串:aabaaa,为了方便这里表示,将这五个字符依此用①②③④⑤⑥来表示。如果我们匹配成功了①,而匹配失败了②,我们接下来应该用①来尝试匹配;如果我们匹配成功了②,匹配失败了③,我们应该使用②来尝试匹配,因为对于子字符串aa,它的前缀a和后缀a是相同的,由于前一个字符位置上匹配成功了②,所以①也必然匹配前一个字符,所以直接使用②来尝试匹配当前字符;中间略过几种情况,假如我们已经匹配成功了④和⑤,当前字符匹配失败了⑥,那么我们接着应该直接用③来尝试和当前的字符匹配,原因是前缀①②与后缀④⑤相同。【前缀能不包括最后一个字符,同样地,后缀也不能包括第一个字符】

为了确定中间应当略过几个字符,使用KMP方法时,需要预先根据模式字符串建立一个数组,假设叫做kmp[],其中kmp[i]存储的是前i + 1个字符中,最长的前后缀相同子字符串的长度,对于上边的aabaaa,kmp[0]表示子字符串a,故kmp[0] = 0;kmp[1]表示的是子字符串aa,由于最长前缀a和后缀a相同,所以kmp[1] = 1;kmp[2]表示的是子字符串aab,前缀a、aa都无法与任何后缀b、ab相同,所以kmp[2] = 0;由此可接着得到kmp[3] = 1, kmp[4] = 2, kmp[5] = 2.

实现的时候,我们可以这样做:首先让kmp[0] = 0,之后给定一个变量k = 0,可以理解成当前第一个要匹配的字符,也就是除去当前长度下最长相同前后缀后的第一个字符在模式字符串数组中的位置,接下来我们从i = 1开始遍历模式字符串,对于每个字符,尝试将pat[k]与pat[i]匹配,如果成功匹配,就可以将k加1,并且将这个值放入到kmp[i]中;如果匹配失败,则将k尝试去上一次的值,也就是在比当前字符少一个字符时的最大相同前缀后的一个字符的位置,即kmp[k – 1]的值,如果仍然不匹配,则继续这样做,直到匹配或k到达0。当k到达0时,pat[0]即是第一个字符,如果它仍然不能和当前字符匹配,则说明kmp[i] = 0,反之则是只有这一个字符匹配成功,kmp[i] = 1。这样就可以建立好kmp数组。

再次说明一下:kmp[i]表示的是模式字符串前i + 1个字符中,最长的相同前后缀的长度,假设长度为L,由于模式字符串中的字符下标从0开始,所以刚好0~L – 1就是这个前缀,每次比较便可以从L处开始,即kmp[i]处开始。

用类似的办法来进行模式匹配,从k = 0、i = 0开始,匹配模式字符串pat[k]与长字符串txt[i],如果相同,就k++, i++后接着匹配,其间留意检查k是不是已经达到pat字符串的长度,是的话,要将它的值置为kmp[k – 1]。

还有一点注意点是:由于下面代码while循环中的一个条件是k < 0,所以即便结束了这个循环也无法保证一定是匹配成功,可能仅仅是因为k归0了,所以要再用if来判断是否匹配成功。

C++实现如下:

#include <iostream>

using namespace std;

const int LIM = 10;             /* The maximum length of pattern string */
int kmp[LIM];

void build(string &pat) {
    kmp[0] = 0;
    int k = 0;
    int len = pat.size();
    for (int i = 1; i < len; i++) {
        while (k > 0 && pat[k] != pat[i])
            k = kmp[k - 1];
        if (pat[k] == pat[i]) kmp[i] = ++k;
        else kmp[i] = 0;
    }
}

void kmpSearch(string &txt, string &pat) {
    build(pat);
    int k = 0;
    int len = txt.size();
    int pl = pat.size();
    for (int i = 0; i < len; i++) {
        while (k > 0 && pat[k] != txt[i])
            k = kmp[k - 1];
        if (pat[k] == txt[i]) k++;
        else k = 0;
        if (k == pl) {
            /*
             *  found the pattern string
             *  do something here
             */
            k = kmp[k - 1];
        }
    }
}

int main(void) {

    return 0;
}

如果模式字符串比LIM设定的大,需要修改LIM的值。

成功匹配到模式字符串后进行的操作,请放在/* do something here */注释后。

上边实现的关键:(1)kmp数组的下标表示长度为下标+1的子串,值是该子串的最大相同前后缀长度,因此匹配失败时k赋值kmp[k – 1]。(2)kmp数组中的值虽然是最大相同前后缀的长度,但也恰好是模式串中接下来需要尝试匹配的字符的序号(如果字符串的序号是从0开始的话)。(3)回到k = 0跳出循环后也要记得再做一次判断,决定是否要增加k。

 

相关阅读:

Brute Force Pattern Search

 

相关问题:

【HDU – 1711】Number Sequence【KMP】