KMP算法

KMP算法是一种基于BF算法改进的字符串匹配算法
由D.E.Knuth，J.H.Morris和V.R.Pratt于1977年联合发表
取三位大佬的姓氏首字母命名为KMP算法

算法核心：

• 构建模式串的next数组

要点：

1. next[0]位置没有前后缀置-1，next[1]位置前后缀相同置为0
2. 匹配成功则i++ && ++n，++n的原因为：next[i]最多比next[i-1]多一个
3. 失败时可以利用前面匹配过的结果：

• n != 0=>n = next[n]
• n == 0=>next[i++] = 0

获得next数组后我们就可以加速主串与模式串的匹配：

• 时间复杂度：O（N + M）

• 空间复杂度：O（M）

Talk is cheap. Show me the code!

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int KMP(string);
vector<int> getNext(string);

int KMP(string str1, string str2) {
    if (str1.size() < str2.size() || str2.empty())
        return -1;
    vector<int> next = getNext(str2);
    int i1 = 0;
    int i2 = 0;
    while (i1 < str1.size() && i2 < str2.size()) {
        if (str1[i1] == str2[i2]) {
            i1++;
            i2++;
        }
        else if (next[i2] == -1) {
            i1++;
        }
        else {
            i2 = next[i2];
        }
    }
    return i2 == str2.size() ? i1 - i2 : -1;
}

// 算出str的每个位置的最长前后缀匹配长度
vector<int> getNext(string str) {
    if (str.size() == 1)
        return { -1 };
    vector<int> next(str.size(), -1);// nexts[n]表示，str[0~n-1]的字符串最长前后缀匹配长度
    next[0] = -1; next[1] = 0;
    int i = 2;
    int n = 0;
    while (i < next.size()) {
        if (str[i - 1] == str[n]) {
            next[i++] = ++n;
        }
        else if (n > 0){
            n = next[n];
        }
        else {
            next[i++] = 0;
        }
    }
    return next;
}