KMP及其应用

2016-06-15

简介

KMP是经典的字符串匹配算法。假设子串长度为M，母串长度为N，暴力的字符串匹配的时间复杂度为\(\Theta(M*N)\), 因为对于母串中的N个字符，每个字符与字串比较的复杂度都可能是\(\Theta(M)\)。

KMP算法能将时间复杂度降到\(\Theta(N)\)。其中最重要的计算next数组。

KMP的核心——计算next数组

我们定义next数组的长度等于子串的长度M。next[i]表示必须以match[i-1]结尾的后缀子串（不包含match[0]!）与必须以match[0]开头的前缀子串（不包含match[i-1]!）的最大匹配长度是多少。

对所有match，我们定义next[0] = -1, next[1] = 0。

简单的例子：

假设 match = “aaaab”, 则match的next数组中，在b位置，next[4] = 3。因为对于”aaaa”，最大的前缀与后缀匹配为”aaa”。

下面直接给出求next数组的代码。

vector<int> getNextArr(string ms){
    vector<int> next(ms.size(), -1);
    if (ms.size() == 0 || ms.size() == 1){
        return next;
    }
    next[0] = -1;
    next[1] = 0;
    //从下标2开始
    int pos = 2;
    int cn = 0;
    while(pos < ms.size()){
        if (ms[pos - 1] == ms[cn]){
            next[pos++] = ++cn;
        }
        else if (cn > 0){
            cn = next[cn];
        }
        else{
            next[pos++] = 0;
        }
    } 
    return next;
}

求得next数组后，比较子串与母串就变得高效多了。

KMP字符串匹配代码：

int getIndexOf(string &s, string &m){
    if (s == NULL || m == NULL || m.size() < 1 || s.size() < m.size()){
        return -1;
    }
    int si, mi;
    si = mi = 0;
    while(si < s.size() && mi < m.size()){
        if (s[si] == m[mi]){
            si++;
            mi++;
        }
        else if (next[mi] != -1){
            mi = next[mi];
        }
        else{
            si++;
        }
    }
    return mi == m.size() ? si - m.size() : -1;
}

应用

有些问题可以抽象成KMP的求next数组，遇到了我会继续更新在下面。

最短回文串

leetcode 214: Shortest Palindrome

题目要求只能在首字母前面添加字符串，所以题目抽象为求字符串中的最长回文子串，该子串必须包含首字母。

思路是将字符串s先翻转，然后将其连在s后面构成一个新的字符串。#的作用是防止计算next数组时计算的长度超过原字符串s的长度(假设s只含a~z)。

1
2
3

string s_rev = s;
reverse(s_rev.begin(). s_rev.end());
string combineS =  s + "#" + s_rev;

利用求next数组的思想，可以得到s串含首字符最长回文子串，然后将剩余的部分反向加在s前面即获得了题目要求的Shortest Palindrome串。

Code

getNextArray函数为求next数组的函数，上面已经给出，本题可以只返回next[next.size() - 1]的值即可，我懒得改了。

string shortestPalindrome(string s) {
    if (s.size() == 0) return "";
    string oriS = s;
    reverse(s.begin(), s.end());
    string combS = oriS + "#" + s + "#";
    vector<int> next = getNextArray(combS);
    int index = next[next.size() - 1];
    if (index < oriS.size()){
        string add = oriS.substr(index);
        reverse(add.begin(), add.end());
        return add + oriS;
    }
    else{
        return oriS;
    }
}