edfward

嘿,KMP

近来清扫 Pocket 存货的时候发现了一些 KMP 算法的东西,以前一直没看,这下一鼓作气扫了一遍顺便刷了刷 POJ 上相关的题,于是来做个总结。

KMP (Knuth-Morris-Pratt) 是以三个大牛的首字母命名的,目的是在文本字符串 T 中寻找完全匹配模式串 P 的位置。简单的例子:

T, P = 'ABABAC', 'BAC'
index = KMP(T, P) # =>3

显而易见的做法是暴力匹配,把 T 挨个扫一遍,每个位置都和 P 比较一番。很容易想象出这个实现需要两个 for 循环,故而时间复杂度为 O(len(T)*len(P)), 虽然内循环很容易就 break。KMP 只需要 O(len(T)+len(P)))。

看了很多版本关于这个算法的介绍,觉得都不是很好理解。我也试试用一个例子来解释:

pos:   0 1 2 3 4 5 6 7 8 9
T:     O A B C A B C Y
P:       A B C A B D X
P':            A B C A B D X 

模式串 P 匹配 T 到第6号位匹配失败,如果是前面提到的暴力搜索的话下一步就是从 T[2] 处重新开始匹配 P,然后不停的失败直到在开头在4号位的 P’ 于6号位匹配成功继续比较7号位。KMP 算法的目的就是希望省略中间无意义的试错,直接跳到结果:虽说 T 和 P 在6号位不匹配,但是上帝告诉我下一步直接试试比较 T[6] 和 P[2]就行啦,成功的话继续不成功的话再想办法重新开始。

这里的“上帝“相当于一个函数(取名叫 next 吧),给我匹配失败的位置信息,我给你下一步比较的对象,无重复无遗漏也不需要回溯,那一定是极好的。那匹配失败的位置信息是什么呢,就是 P 中该位置的下标(所以这个例子中 next(5)=2,先前 P[5] 和 T[6] 不匹配,下一步就比较 P[2] 和 T[6],看起来就像 P 串直接右移了三位)。为了得到这个函数我们要观察一下,不难发现 P’ 的前两位和 P 的3、4位相同。稍微动动脑筋就能把这个现象归纳成如下的形式:

假设 next(i) = j, 那么必须满足 P[0]=P[i-j], P[1]=P[i-j+1],…P[j-1]=P[i-1]

这个归纳可以得到如下结果:

  1. next 只需记录 len(P) 那么多的值就行了
  2. next 只与 P 有关,只要先前预处理好,那么比较 T 与 P 的工作量就会大大减小

用刚刚归纳的条件直接实现 next 的话代码是这样的

for (int i=1; i < size; ++i) {
    for (int j=0; j < size-i; ++j) {
        if (P[j] == P[i+j] && next[i+j+1] == 0) {
            next[i+j+1] = j+1;
        }
        else break;
    }
}

next 被初始化为0,第三行多了一个 next[i+j+1] 不能被动过的条件。这是为了让 P 串不会由于 next 值的移动步子太大造成遗漏。

再认真想一下,这个代码片段本身不正是在匹配字符串吗?只有当 P[0..j-1] 和 P[i-j..i-1] 相等的时候我们才有机会更新 next[i] 的值。 那我们就试试用 next 数组来求 next 吧(实际上是通过已经得到的 next 来求剩下位置的值):

void find_next(const string& p) {
    pattern = string(p); // init private data member
    int sz = pattern.size(), j = 0, i = 1;
    next = vector<int>(sz+1);
    next[0] = -1;
    while (i < sz) {
        if (j == -1 || pattern[i] == pattern[j]) {
            next[++i] = ++j;
        }
        else {
            j = next[j];
        }
    }
}

i 和 j 的地位和上面那个例子相同。next[0] 不会被用到所以这里用一个小技巧来让它作为标志:i 和 j 同时自增的情况只有两种,其一是 j 匹配失败而对应的 next 值为0所以 j 一定会回到-1,这时两者自增相当于用来比较的 P 串右移了一位然后继续比较 P[i] 和 P[0],对 next 数组无影响(因为本身就初始化为0了),其二是 P[i] 与 P[j] 相等,ok 那就更新 next 数组。由于 j 大多数情况都小于 i, 所以 j 在跳转到 next[j] 的时候这个 next 值已经在之前求出来了。

顺带一说提交 POJ 3461 时这两个版本的 find_next 函数都试过,前者耗时 277ms 后者耗时 250ms,似乎区别没那么大。

用相同的思路利用得到的 next 做匹配:

int pattern_match(const string& source) {
    int s_len = source.size(), p_len = pattern.size();
    int si = 0, pi = 0, cnt=0; // index of source and pattern
    while (si < s_len) {
        if (pi == -1 || source[si] == pattern[pi]) {
            ++si, ++pi;
        }
        else {
            pi = next[pi];
        }
        if (pi == p_len) {
            cnt++;
            pi = next[pi];
        }
    }
    return cnt;
}

这个函数寻找 source 串里出现了多少次模式串 pattern,连写法基本上都与 find_next 函数一样。

掌握这个算法之后可以刷一下 POJ 上这几道题,都是在对 next 数组的理解上做文章。

3461 – Oulipo, solution: kmp_occurrence.cpp
2406 – Power strings, solution: kmp_power_string.cpp
1961 – Period, solution: kmp_period.cpp
2752 – Seek the Name, Seek the Fame, solution: kmp_cat_name.cpp