KMP

1.作用

用于字符串匹配，在文本串 $S$ 中查找模式串 $P$ 。（较短的或许直接调用函数？）

2.过程（结合画图分析）

KMP算法相较于朴素算法的精髓在个人看来在于不回退指针 $i$，以及 $Next[i]$ （模式串在位置 $i$ 以前的子串的最长公共前后缀）。

为什么不用回退 $i$ ？

在 $i$ （匹配失败的位置）之前模式串匹配成功的字符有两种情况：每个字符都不相同、部分字符相同

每个字符都不相同 ：因为相应位置的字符已经和文本串匹配，那么可以表明已经匹配的字符中不会有一个位置可以使文本串与模式串匹配。

部分字符相同 ： （再次划分）

相同部分在两端（即前后缀）：看下面分析。（先写的下面发现忘了这个。。）

相同部分不在两端（A，B至少有一个不是前后缀）：将相同的部分在前面的一段称为子串 $A$ ，后面的称为子串 $B$，那么假设把 $A$ 移动到 $B$ 的位置：那么如果 $A$ 不是前缀，则在 $A$ 之前的那部分无法与原本在 $B$ 之前的子串匹配，如果 $B$ 不是后缀，那么在 $A$ 之后的那部分无法与原本在 $B$ 之后的子串相匹配（注意只有 $A$ ，B这部分相等，如果匹配说明它们的长度还能更长），因此也是无法找到位置使得文本串与模式串匹配。

综上所述没有回退 $i$ 的必要。

为什么要找出最长公共前后缀？

假设字符串在第 $i+1$ 位时匹配不成功，那么在 $[0,i]$ 这个区间上的字符串是可以匹配成功的，假设存在某段前缀等于某段后缀（注意前后缀不包括字符串本身），那么我们可以将这段前缀往右移，到原本后缀的位置，那么此时 原本的前缀 可以 和 原本的后缀相匹配的 那一段文本串的子串 匹配，如果通过移动使得原本不匹配的位置又可以成功匹配，那么就继续往后匹配，否则继续看 移动后的模式串 在当前位置的子串 是否还有相等的前后缀，如果有则继续上述操作，否则让模式串重新开始匹配。

以下是找出最长公共前后缀的代码

    const int N = 1e6 + 10;
    Next[N];
    string s; cin >> s;
    Next[0] = -1;
    for (int i = 1, j = -1; i < n; i++) {
        while (j != -1 && s[i] != s[j + 1])j = Next[j];
        if (s[i] == s[j + 1])j++;
        Next[i] = j;
    }

匹配

for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != p[j + 1])j = Next[j];
        if (s[i] == p[j + 1])j++;
        if (j == m) {
            cout << i - m + 1 << endl;
        }
    }