KMP算法

算法

问题描述:

给定一个文本串S, 和一个模式串P, 我们要找到P在S中的位置，即给出P的第一个字符在S中的位置。

朴素算法 #

枚举S中每个位置，判断是否是模式串P的起点。

基于上述思想，我们可以很容易可以写出如下的枚举代码:

int vanilla_find(const string& s, const string& p) {
    int pos = -1;
    bool ok = true;
    for(int i=0; i<s.size(); i++) {
        ok = true;
        for(int j=0; j<p.size(); j++) {
            if(s[i+j] != p[j]) { ok = false; break; }
        }
        if(ok) { pos = i; break; }
    }
    return pos;
}

上述实现使用1个循环枚举配对的起点，再用1个循环判断从该起点开始是否有模式串P。

为了方便理解KMP算法，我们不妨换一种思路实现这个朴素算法。

int vanilla_find2(const string& s, const string& p) {
    int i=0, j=0;
    while(i < s.size() && j < p.size()) {
        if(s[i] == p[j]) { i++; j++; } 
        else { i=i-j+1; j=0; }
    }
    if(j == p.size()) return i-j;
    else return -1;
}

上述实现使用两个指针, i, j，i指针代表当前S串匹配到的位置，j表示P串匹配到的位置，遇到不匹配，则将i指针回溯到上一次尝试的起始点的后一个位置，即i-j+1。j指针回溯到开头。

虽然两种实现本质是一样的，但第二种实现会更容易理解KMP算法的优化。

如图1所示，当我们匹配成功ABCDAB后，发现D不匹配，这时如果我们将i回溯到i-j+1的位置，匹配必然失败，因为我们前一步已经知道S[i-j+1]=B了。

如果我们能够利用前一步的匹配结果，让i不必回溯，只回溯j的话，那么匹配效率会大幅提升。

{% include double-image.html url1="/assets/img/kmp1.png" caption1=“Step1” url2="/assets/img/kmp2.png" caption2=“Step2” size=“70%” description=“图1” %}

KMP算法 #

如果我们把之前的优化假设形式化一下，我们将得到如下的描述。

当失配时，我们希望能够让i=i,j=next[j]，即i不用回溯，j根据当前位置决定模式串要跟S[i]匹配的位置。

事实上，这个假设是成立的，考虑如图2的情况：

{% include double-image.html url1="/assets/img/kmp3.png" caption1=“Step1” url2="/assets/img/kmp4.png" caption2=“Step2” size=“70%” description=“图2” %}

当D失配时，我们知道模式串的D之前有相投的前缀后缀AB，因此我们只需要尝试匹配模式串前缀AB后的D以及文本串的 即可。

换句话说，我们知道这时候next[j]=2。

如此，现在的问题就变成如何求next数组了。

求解next数组 #

让我们再次考虑图2的情况，事实上，我们已经能够发现求解next[j]的规律了。对于P串的第j个元素，其失配后需要回溯到的位置取决于 - P串前j个元素有多长相同的前缀后缀。如果有长度为k的相同前缀后缀，则next[j]=k。

基于上述思想，我们其实已经可以编写一个暴力求next数组的程序了。

vector<int> get_next_vanilla(const string& p) {
    vector<int> next(p.size());
    next[0] = -1;
    for(int i=1; i<p.size(); i++) {
        int n_match = 0;
        // 枚举所有可能的相同前缀后缀
        for(int k=1; k<i; k++) {
            bool ok = true;
            for(int j=0; j<k; j++) {
                if(p[j] != p[i-k+j]) ok = false;
            }
            if(ok == true) n_match = k;
        }
        next[i] = n_match;
    }
    return next;
}

很显然，这种暴力求解的效率是很低的($$O(n^3)$$)。因此，我们需要对求解next的算法进行优化。

递推求解优化 #

考虑下面这种情况

ABCDABDC
01234567

如果我们已经求得next[6]=2，即D之前有相同前缀后缀AB，那么我们在求next[7]的时候，只需要判断P[next[6]] == P[7-1] (C==D)是否成立即可。

  • 若成立，显然next[7] = next[6] + 1。
  • 若不成立，那么我们需要考虑D要和AB这个前缀中的哪个字母进行配对组成相同前缀后缀。（其实这是一个套娃问题:》）

换句话说，我们在求next[i]的时候我们实际上需要的是，P[:i-1]中最长的相同前缀后缀（可以通过next[i-1]得到），设长度为k, 然后再判断P[l] == P[k]。如果不等于的话，我们就找出P[:k-1]中第二长的相同前缀后缀，用同样方法再判断一次。

实际上，第二长的相同前缀后缀可以通过next[next[k-1]]得到。

为什么？第一长的相同前缀后缀的相同前缀后缀实际上就是第二长的相同前缀后缀。例如 ABABCDABAB, 第一长是 ABAB, 第二长是 AB

基于上述思想，我们可以写出如下的递推求解的代码

vector<int> get_next(const string& p) {
    vector<int> next(p.size());
    next[0] = -1;
    for(int i=1;i<p.size();i++){
        int k=i-1;
        while(k!=0 && p[i-1] != p[next[k]]) k=next[k];  // 先找出"OK"的前缀后缀
        next[i] = next[k] + 1;
    }
    return next;
}

继续优化 #

优化1

我们首先可以重构一下代码, 以下代码和get_next等价。

vector<int> get_next2(const string& p) {
    vector<int> next(p.size());
    next[0] = -1;
    int i=0, k=-1;
    while(i < p.size() - 1) {
        if(k == -1 || p[i] == p[k]) {
            i++; k++;
            next[i] = k;
        } else { k = next[k]; }
    }
    return next;
}

优化2

再者，考虑如下情况

abab
next: -1, 0, 0, 1

当b失配时，next=1，但是P[1]=b，我们没必要再比一次，因为这次一定失配，基于此我们可以再次优化。如下所示：

vector<int> get_next2_opt(const string& p) {
    vector<int> next(p.size());
    next[0] = -1;
    int i=0, k=-1;
    while(i < p.size() - 1) {
        if(k == -1 || p[i] == p[k]) {
            i++; k++;
            // 以下两行为优化内容
            if(p[k] != p[i]) next[i] = k; 
            else next[i] = next[k];
        } else { k = next[k]; }
    }
    return next;
}

原来的get_next当然也可以用同样的方法优化，但是要注意写法。 下面这种优化方式就不行。事实上，当你把下面的代码改对之后，你会发现你的代码就变得和get_next2_opt基本一样了。

vector<int> get_next_opt(const string& p) {
    vector<int> next(p.size());
    next[0] = -1;
    for(int i=1;i<p.size();i++){
        int k=i-1;
        while(k!=0 && p[i-1] != p[next[k]]) k=next[k];  // 先找出"OK"的前缀后缀
        // 直接这样优化是不行的
        if(p[i] != p[next[k]+1]) next[i] = next[k] + 1;
        else next[i] = next[next[k]+1];
    }
    return next;
}

参考资料 #

  1. 从头到尾彻底理解KMP: cnblogs
Calendar May 28, 2023