KMP 算法

KMP算法是关于字符串匹配的一个算法。

比如说有一个字符串是 “acbabcdabdbacdd”

我们要在这个字符串中寻找是否有子串 “acbdacd”，有就返回下标，没有就返回-1

暴力匹配

暴力匹配的思路

这个题目我们的思路其实是非常明确的。那就是暴力匹配呗。

如果匹配了我们就返回，如果不匹配我们就重新开始匹配下一个字符。

上面的那个题目，匹配到第四个个字符不匹配了，那么我们把子串往后移后一位，用a和c再比较。。。

这个暴力匹配就是一旦遇到了不匹配的字符，就把子串移后一位，如果都到了主串的末尾了还没有匹配成功，那么就说明这个主串中没有子串，返回-1即可。

代码实现的其实也蛮简单的。

暴力匹配代码实现

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

/**
 * 使用暴力算法，就是这么的暴力！！
 */
int KMP(string str, string sub) {
    // 使用i来指向主串，使用j来指向子串
    int i = 0, j = 0;
    // 主串还没有被比较结束
    while (i < str.length()) {
        // 匹配了 继续比较下一位
        while (str[i] == sub[j]) {
            i++;
            j++;
            // 匹配成功，在主串中发现了子串
            if (j == sub.length()) {
                return i - j;
            }
        }
        // 匹配失败，将i移动到本次匹配的后一位
        i = i - j + 1;
        // 重置子串， j重新指向子串的开头
        j = 0;
    }

    return -1;
}

int main(int argc, char const *argv[]) {
    string str = "BBC ABCDAB ABCDABCDABDE";

    string sub = "ABCDABCDE";

    int index = KMP(str, sub);
    if (index == -1) {
        cout << "Not Found!" << endl;
    } else {
        cout << "Found!\nT/F: "
             << (str.substr(index, sub.length()) == sub ? "True" : "False")
             << endl;
    }

    system("pause");
    return 0;
}

这个暴力匹配的算法，就算是个小学生也能一眼看懂吧，不需要做什么代码说明了，重点戏是后面的KMP算法。

暴力匹配：时间复杂度是O(mn) 其中m是子串的长度，n是主串的长度.

KMP 算法

关于暴力匹配的思考及KMP的思路

暴力匹配的算法每次都是后移一位。比如下面

主串: abcdxxxx
子串: abcde

我们发现第五位不匹配，暴力匹配的思路是这样子的，移动到下一位

主串：abcdxxxx
子串： abcde

但是这个不是很脑残的行为吗？既然第五位是不匹配的，那么主串和子串的前四位不就都是相等的吗？我们再次观察这个子串的前面的四位都是不相同的字符，那么我们完全没有必要让子串a再次和后面bcd比了。我们完全可以直接跳到这一步

主串: abcdxxxx
子串:     abcde

i直接往前跳了四步，极大的节省了时间。

但是问题就在，你是怎么知道前面的四位都是不相等的?

主串: ababxxxx
子串: ababe

这次也是第五位不匹配的，这次我们还是跳四位？？？

这时有人要抢答了：同学，这里有两个相同的字符，这傻子都可以看出来是跳两位啊！！

那么这个也是跳两位？

主串: abbaxxxx
子串: abbae

很明显这个是跳三位。我们看起来非常的容易，一看就知道跳几位，但是如何用逻辑描述这个到底应该跳几位了？

我们到第5位不匹配要跳几位，其实和第五位没有关系，这完全取决与前面的四位。我们来观察一下：

abcd -> 4 = 4-0
abab -> 2 = 4-2
abba -> 3 = 4-1

或许也许可能观察不出来什么，不过观察一下他们的前缀和后缀。

比如 impossible 前缀就有im 后缀就有ible 但是他们的前缀和后缀不能是他们的本身

字符串 前缀 后缀 前缀后缀共有字符串的最大长度
abcd a, ab, abc d, cd, bcd 0
abab a, ab, aba b, ab, bab 2
abba a, ab, abb a, ba, bba 1

这样就明白了吧，我们往后移动的多少取决于前缀后缀共有字符串的最大的长度。

我们可以来验证一下

主串: BBC ABCDAB ABCDABCDABDE
子串: ABCDABD

第一步：（找到第一个匹配的位置）

主串: BBC ABCDAB ABCDABCDABDE
子串:     ABCDABD

第二步：(C和空格不匹配)

ABCDAB的前缀后缀的共有字符串是2，那么应该向后移动6-2=4位

主串: BBC ABCDAB ABCDABCDABDE
子串:                ABCDABD

发现找到了

我们可以发现KMP的思路其实还是蛮清晰的。就是这个简答，利用匹配失败已经前面匹配成功的字符的前缀后缀共有字符串的最大的长度来尽可能多的往后移动位置，反观暴力破解，每次就只是往后面移动一位d，效率低下。

KMP寻找的时候的时间复杂度是O(n)

构造部分匹配表

上面的那个由前几位前缀后缀共有字符串的最大长度构成的表被称为部分匹配表。那么如果用代码去构造这个部分匹配表呢？

比如如下的字符串，部分匹配表如下(第三行)，但是如何去构造呢

 0 1 2 3 4 5 6 ---(序号)
 a b c d a b d ---(字符串)
 0 0 0 0 1 2 0 ---(部分匹配表)
 1 1 2 3 4 4 4 ---(到这一位不匹配的时候向后移动的位数)

思路

  a b c d a b d
1 j i          ->0    
2 j   i        ->0
3 j     i      ->0
4 j       i    ->1
5   j       i  ->2    
6     j       i

这个第六步发现i位和j位不相等，那么i是肯定不能动的，动的肯定是j那么j怎么变？j变成0？？？
此时j-1的字符肯定是等于i-1处的字符的。此时我们想要知道是否j还有别的值的前一位是等于i-1的然后跳到这个j
这个例子中没有下面再举一个例子
   a b c d a b d
 a b c d a b d
 ...
         a b c d a d b
 a b c d a b d
 0 0 0 0 1 2 
 此时我们发现d和c不匹配，我们想从a b中找到可能和b相等的值
 d处的最大前缀后缀共有的最大长度有可能超过2吗？不可能
 假如如下的字符串
 x y d x y c z z z z x y d x y d
           j                    i   -> [i-1] == [j-1]
 x y d x y c z z z z x y d x y d
     j                         i   -> [i-1] == [j-1]
     此时又回到了j前面的值和i前面的值再次都相等的情况，再次比较,如果不相等回到
x y d x y c z z z z x y d x y d
j                             i  -> x y这个串的前后缀最大已经是0了

上面或许讲的有点乱，因为当时我也是有点乱，但是现在我明白了

我们发现当部分匹配表没有1这个值，没有前缀也没有后缀，就给它一个0吧

int* calNext(string sub){
    int length = sub.length();
    int* next = new int[length];
    next[0] = 0;
    int i=1, j=0;
    while(i < sub.length){
        if (j > 0 && sub[i] != sub[j]){
            j = next[j-1];
        }
        if (sub[i] == sub[j]){
            j++;
        }
        next[i++] = j;
    }
}

代码说明：

这里面最难以理解的估计就是那一句话，就是j = next[j-1]到底是什么含义

比如

 0 1 2 3 4
 a b a b c
     j   i
 0 0 1 2 0

j = next[j-1]之后就是 j =0;

j = next[j-1]的含义就是回到上一个时刻 sub[j-1] == sub[i-1]不仅如此，他们前面的值都是相等的！

这个例子中这样的数不存在

x d x y x d x d
      j       i
这时 j = next[j-1]
x d x y x d x d
  j           i
此时j前面的数和d前面的数又都是相等的了，再次进行比较！如果还是不相等 j = next[j-1]

这样应该很好理解了吧。

这样我们的next数组也就构造好了，KMP算法也就好实现了

KMP 代码

int KMPsearch(string str, string sub, int* next){
    int strLength = str.length();
    int subLength = sub.length();

    int i=0, j=0;
    while (i < strLength && j < subLength){
        // KMP核心，不匹配向后移动
        if (j > 0 && str[i] != str[j]){
            j = next[j-1];
        }
        if (str[i] == sub[j]){
            i++;
            j++;
        }
        if (j == 0 && str[i] != str[j]){
            i++;
        }
    }
    // 找到了子串
    if (j == subLength){
        return i-j;
    }else {
        return -1;
    }
}

代码说明：

其实需要说明的就只是KMP的核心那一块代码。我们一直说什么往后移动，其实这也不是往后移动啊？

其实这只是我们想象中的往后移动，实际上是这样子的

abcdabcde
abcde       -> 上面的a匹配失败
->
abcdabcde
    abcde   -> 让下面a和上面a进行比较

当匹配到第五位的时候，i其实没有变，变的只是j而已我们直接让sub[next[j-1]]和str[i]进行比较

上面那个next[j-1]就是a

abacabab
abab     -> 上面的c匹配失败
->
abacabab
  abab   -> 让下面b和上面c进行比较

再次重申一下，i没有变，变的只是j而已。

总结

写到了这儿KMP算法基本上就写完了，写完了之后我对KMP算法的理解算是有涨了一个层次，至少能基本理解这个算法该如何用了而不是单纯的被代码。其实网上关于KMP算法的博客特别多，每个人使用的方法都是不一样的，我看了很多人的next[0] = -1，还有构造了其他各种各样的数组，我基本上都没怎么看，我看的不是代码是怎么写的，主要是KMP的思路是如何的，理解了这个思路之后，什么样的实现KMP算法的代码基本上都能看懂了。

赏

一枚小菜鸡