KMP算法理解

昨天做了Twitter的OA，最后一题是一个KMP算法的变形，之前看过KMP算法，但是看的不甚仔细，最后还是边学边写才写出来，运气甚好，一次AC。这种OA的环境下，如果不是AC，真是连bug都难看出来。这次整理一遍，下次遇到的时候可不能在靠运气了。

1. brute-force 解决

KMP算法是用来解决字符串匹配问题的。heystack长度为m， needle长度为n，那么最简单的方法是暴力搜索，算法复杂度为O(m * n)

// return -1 if not found, otherwise return the start position
int Strstr(string heystack, string needle) {
    int heystack_size = heystack.size(), needle_size = needle.size();

    for (int i = 0, j; i <= heystack_size - needle_size; i++) {
        for (j = 0; j < needle_size; j++) {
            if (heystack[i+j] != needle[j]) break;
        }
        if (j == needle_size) return i;
    }
    return -1;
}

2. 两个case

这种O(m * n)的算法并不是最优的，为什么呢？因为有很多子问题被重复计算了。什么是重复子问题，我们想象这样一种序列，用”XABCDE”匹配”AAAAAAAAXABCDE”，这个用暴力算法好吗？从结果来看，是好的，为什么？因为每次几乎没有进入到第二个循环里面就往下走了，needle中”X”字符守门守的好。什么时候暴力算法会失效呢？考虑一下用”AAAAA”匹配”AAAACAAAACAAAAA”，每次第二个循环几乎都会走满,每次都功亏一篑。而这第二种情况中就隐藏着重复的子问题。

2.1 case 1

先考虑一个needle字符串”AAABC”，以及一个heystack字符串”AAABDAABC”。

匹配第1步：
heystack: AAABDAABC
          |    
needle:   AAABC

匹配第4步：
heystack: AAABDAABC
              |
needle:   AAABC

注意：以上的递增是以needle为轴的递增

Brute-Force: 失效，heystack为轴递增1步
heystack: AAABDAABC
           |
needle:    AAABC

KMP: 失效，根据needle的信息，以heystack为轴递增多步
heystack: AAABDAABC
              |
needle:       AAABC

对于我们已经匹配成功的pattern(pattern == “AAAB”，这是needle的一个substring), 我们观察pattern中以左边为开始的substring：A AA AAA，和以B为结束的substring B AB AAB，我们注意到两两并不匹配，那么意味着，即便我们将needle左移任意长度(这部分其实是pattern的substring prefix)，也不会匹配到pattern的任何前缀(substring prefix)，在这种情况下我们已经没必要左移needle，不妨将needle归零，heystack步进一位。

值得注意的是，以上的信息是由needle得到的，与heystack无关，这意味着这个撤回的信息可以提前由needle的信息进行计算。

2.2 case 2

再先考虑另一个needle字符串”AABAAC”，以及一个heystack字符串”AABAABAAC”。

匹配第1步：
heystack: AABAABAAC
          |    
needle:   AABAAC

匹配第4步：
heystack: AABAABAAC
               |
needle:   AABAAC

注意：以上的递增是以needle为轴的递增

Brute-Force: 失效，heystack为轴递增1步
heystack: AABAABAAC
           |
needle:    AABAAC

KMP: 失效，根据needle的信息，以heystack为轴递增多步
heystack: AABAABAAC
               |
needle:      AABAAC

这个案例与之前不同的地方在于，pattern(我们称已经匹配的substring为pattern， pattern等于”AABAA”)中有以左边为开始的substring: A AA AAB AABA，和右边为开始的substring A AA BAA ABAA有重复的部分AA(AA is a substring that is prefix and also a suffix, 一个既是前缀也是后缀的子串)，这意味着我们应该将needle左移两个位置，重新开始匹配，此时heystack保持原有位置不变。

3. KMP算法

现在问题化为连个问题，1. 如何求最长的共同前缀后缀(LPS:longest prefix is also suffix)； 2. 有了最长前缀后缀后，又该如何进行比较。

3.1 求解LPS(longest prefix which also is suffix)

先解决如何求lps的问题，这个其实也是一个比较trick的部分，但是在很多对于KMP的解释中，都会掠过这个部分。
我们考虑一个字符串S(n)，假设lps[n-1] = c,会有一下几种case:

• case 0: s中的第n个字符(新增的那一个)和s[c]相等，则lps[n] = c+1, 考虑一个字符串”AAACAAA” + ‘C’，当前有 lps(“AAACAAA”) == 3， 添加了’C’后，lps(“AAACAAAC”) = 3+1;
• case 1: 若新增字符不等，且c == 0，这意味着前n-1个字符没有substring既是前缀又是后缀，那么新增了一个和s[0]不等的字符，lps[n] = 0；
• case 2: 若新增字符不等，且c != 0，虽说新增的首字母和lps[c]不匹配，考虑一个字符串”AAACAAA” + ‘A’，当前有 lps(“AAACAAA”) == 3， 但是如果添加的是’A’，lps(“AAACAAAA”)一定不为3，但是有可能会是3或者是2，1，需要一步步递减搜索，直到子串为空串，或找到了一个子串；

void computeLPS(string &needle, vector<int> &lps, int pos) {
    lps[pos] = 0;
    if (pos == 0) return;

    // solve n-1 problem recursively
    computeLPS(needle, lps, pos-1);

    // downward search
    for (int length = lps[pos-1]; length >= 0; length--) {
        if (needle[pos] == needle[length]) {
            lps[pos] = length + 1;
            break;
        }
    }
}

3.2 字符串匹配

最后我们解决字符串匹配的问题，从章节2的两个例子中，我们可以看到一下几种情况：

• case 0: needle和heystack字符相匹配，needle和heystack的指针均向后移动
• case 1: needle和heystack字符不匹配，若当前的已经匹配的pattern的LPS为零，heystack指针向后移动，needle归零，如我们的第一例
• case 2: neelde和heystack字符不匹配，若当前的已经匹配的pattern的LPS不为零，heystack指针维持不变，needle向前回撤，如同我们的第二例，值得注意的是，needle回撤的操作是递归的

代码如下

// assume that we have solved lps problem
vector<int> lps;

int KMP_search(string heystack, string needle) {
    int heystack_size = heystack.size(), needle_size = needle.size();

    int hey_pos = 0, ned_pos = 0;

    while (hey_pos < heystack_size) {
        // case 0
        if (heystack[hey_pos] == needle[ned_pos]) {
            hey_pos++, ned_pos++;
            if (ned_pos == needle_size) {
                // match!
                return hey_pos - ned_pos;
            }
        }
        else {
            // case 1
            if (ned_pos == 0) {
                hey_pos++;
            }

            // case 2
            else {
                // we don't change hey_pos until one find a charater match 
                // or LPS of ned_pos equals to 0
                ned_pos = lps[ned_pos-1];
            }

        }
    }

    return -1;
}

4. 完整实现

可直接编译的版本如下

#include <vector>
#include <string>

using namespace std;

void computeLPS(string &needle, vector<int> &lps, int pos) {
    lps[pos] = 0;
    if (pos == 0) return;

    computeLPS(needle, lps, pos-1);
    for (int length = lps[pos-1]; length >= 0; length--) {
        if (needle[pos] == needle[length]) {
            lps[pos] = length + 1;
            break;
        }
    }
}

int KMP_search(string heystack, string needle) {
    int heystack_size = heystack.size(), needle_size = needle.size();
    int hey_pos = 0, ned_pos = 0;

    vector<int> lps(needle.size(), 0);
    computeLPS(needle, lps, needle.size()-1);

    while (hey_pos < heystack_size) {
        if (heystack[hey_pos] == needle[ned_pos]) {
            hey_pos++, ned_pos++;
            if (ned_pos == needle_size)
                return hey_pos - ned_pos;
        }
        else {
            if (ned_pos == 0)
                hey_pos++;
            else
                ned_pos = lps[ned_pos-1];
        }
    }
    return -1;
}

int main() {
    string heystack("ABABABCABABABCABABABAC");
    string needle("ABABAC");

    int ret = KMP_search(heystack, needle);
    return 0;
}