KMP算法

前缀表的定义：

next数组是用来表示前缀表的。前缀表是用来表示一个字符串中最大相等前后缀的表。
前缀：已第一个字符开头，并在当前下标之前结束的字符串
后缀：已当前下标字符结尾，并在当前下标之前开始的字符串
KMP算法可以加快字符串匹配的原因：比如下面的字符串如果是模式串—>匹配到a a b a a时匹配出错—>举例文本串为：a a b a c ……—> 那么模式串当前不匹配字符下标-1对应的前缀表不为0时，文本串中c之前的字符一定有与模式串开头的字符相对应的—>只需要从模式串不匹配字符下标-1对应的前缀表的下标的字符开始比较（写的有点绕—>就是接着比较模式串str[1]与c是否对应）
Eg: a a b a a f
前缀表：0 1 0 1 2 0
next数组有两种表示方法：一种是next数组为前缀表元素-1,另一种是next数组就等于前缀表的情况。这两种情况本质上是一样的，只是代码实现略有不同：

next数组为前缀表元素-1代码：

#include<iostream>
#include<string>
using namespace std;
//next数组等于前缀表-1的情况
void getNext(int* next, const string& str2) {
    int j = -1;
    next[0] = -1;
    int size = str2.size();
    for (int i = 1; i < size; i++) {
        while (j > -1 && next[i] != next[j + 1]) {
            j = next[j];
        }
        if (str2[i] == str2[j + 1]) {
            j++;
        }
        next[i] = j;
    }
}
int KMP(const string& str1, const string& str2) {
    int Psize = str2.size();
    int* next = (int *)malloc(Psize * sizeof(int));
    getNext(next, str2);
    int j = -1;
    for (int i = 0; i < str1.size(); i++) {
        while (j > -1 && str1[i] != str2[j + 1]) {
            j = next[j];
        }
        if (str1[i] == str2[j + 1]) {
            j++;
        }
        if (j == Psize - 1)
            return i - j;
    }
    return -1;
}
int main() {
    string str1("ababcabccabcacbab");
    string str2("abcac");
    int res = KMP(str1, str2);
    cout << res << endl;
    return 0;
}

next数组等于前缀表的情况：

#include<iostream>
#include<string>
using namespace std;
//next数组等于前缀表的情况
void getNext(int* next, const string& str2) {
    int j = 0;
    next[0] = 0;
    int size = str2.size();
    for (int i = 1; i < size; i++) {
        while (j > 0 && next[i] != next[j]) {
            j = next[j - 1];
        }
        if (str2[i] == str2[j]) {
            j++;
        }
        next[i] = j;
    }
}
int KMP(const string& str1, const string& str2) {
    int Psize = str2.size();
    int* next = (int *)malloc(Psize * sizeof(int));
    getNext(next, str2);
    int j = 0;
    for (int i = 0; i < str1.size(); i++) {
        while (j > 0 && str1[i] != str2[j]) {
            j = next[j - 1];
        }
        if (str1[i] == str2[j]) {
            j++;
        }
        if (j == Psize)
            return i - j + 1;
    }
    return -1;
}
int main() {
    string str1("ababcabccabcacbab");
    string str2("abcac");
    int res = KMP(str1, str2);
    cout << res << endl;
    return 0;
}