KMP算法是一种高效的字符串模式匹配算法。 字符串的模式匹配是指在主串S中寻找子串T的过程，其中T称为模式。例如，给定两个字符串S和T，我们需要在S中找到T的位置。

暴力匹配（朴素模式匹配） 设i为主串S的下标，j为模式T的下标。如果当前字符匹配成功（即S[i] = T[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i] != T[j]），则令i = i - (j - 1)，j = 0。这意味着每次匹配失败时，i回溯到本次失配起始字符的下一个字符，j回溯到0。

int BF(char S[], char T[]) {
    int i = 0, j = 0;
    while (S[i] != '\0' && T[j] != '\0') {
        if (S[i] == T[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (T[j] == '\0') return (i - j); // 主串中存在该模式返回下标号
    else return -1; // 主串中不存在该模式
}

KMP算法是一种改进的模式匹配算法，由D.E.Knuth、V.R.Pratt、J.H.Morris于1977年联合发表。KMP算法的改进在于：每当从某个起始位置开始一趟比较后，在匹配过程中出现失配时，不回溯i，而是利用已经得到的部分匹配结果，将指针在模式上向右滑动尽可能远的一段距离，然后继续进行下一次的比较。

前缀与后缀

• 前缀：包含首字符但不包含尾字符的所有子串。
• 后缀：包含尾字符但不包含首字符的所有子串。

最长相等前后缀的长度next数组 例如，对于字符串P=abaabca，各个子串的最大相等前后缀长度如下表所示：

字符	最长相等前后缀长度
a	0
b	0
a	1
a	1
b	2
c	0
a	1

这个表表示在当前字符作为最后一个字符时，当前子串所拥有的公共前后缀最长长度。例如，当c作为最后一个字符时，当前子串abaabc并没有公共前后缀。

接下来我们使用这个表来生成next数组，next数组的值是公共前后缀最长长度。我们称next数组中的值为失效函数值。

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

void generateNext(int *next, const string &pattern) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < pattern.size() - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmpSearch(const string &text, const string &pattern) {
    int *next = new int[pattern.size()];
    generateNext(next, pattern);
    int i = 0, j = 0;
    while (i < text.size() && j < pattern.size()) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    delete[] next;
    if (j == pattern.size()) return i - j;
    return -1;
}

int main() {
    string text, pattern;
    cin >> text;
    cin >> pattern;
    cout << kmpSearch(text, pattern) << endl;
    return 0;
}
/*
输入
babaabaabaafg
aabaaf
输出
6
*/