AcWing 831.KMP字符串

摘要：
闪耀着人类智慧之光的——KMP算法。

题目

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。

输入格式
第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串S。

输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。

数据范围
$1≤N≤10^5$, $1≤M≤10^6$

输入样例：

3
aba
5
ababa

输出样例：

0 2

---

思路

模式串S______Sa__________N______________
模板串P######Pa__________N
假设当 S 和 P 从 a 点开始匹配时，到 N 点恰好发现一个字符不匹配，暴力做法我们是让 P 向右偏移一位，从头开始和 S 一一比对。但是存在一些字符是之前已经比对匹配过的，我们可以跳过它们以达到优化目的。
我们现在的目标就变成了： 如何利用已经比对匹配过的字符已达到优化目的？
设想如果我们能找到这样一个平移量 x 使得当我们把 P 串向右移动 x 位时：
模式串S______Sa___x________N______________
模板串P######Pa___x________N
模板串P##########Px________N_____（移动x位后的）
恰好使得在 P 串和 S 串中从 x 点到上次出现不同字符的 N 点中所有数相同，那么如果发现了这个 x 值，就可以从这里开始让两串匹配，从而完成优化。
即 P 串移动一个 x 使得 P 串的某一前缀与 S 串的后缀完全相等，在移动前， S 串的后缀与 P 串后缀已经比较过，完全相等。那么问题就转化成，能否找到这样一个 x 使得，在 P 串内部， P 串的前缀与后缀完全相等。 x 和前后缀的关系是： x + 前缀或后缀 == Pa_N 。（这里的前后缀是相对 Sa_N 和 Pa_N 而言）。
以上叙述可形象的看成：
模板串P|___x___|_______suf_______|
模板串P########|_______pre_______|___x___|
其中， suf == pre 。
当我们找到了这个 x 还远远不够，因为可能存在多个这样的 x ，为了使优化效果最好，我们尽可能地希望这个 x 越小越好（ x 最小可取到 1 ，因为后面已经发生不匹配情况，如果取 0 的话造成矛盾）,当 x 取到 1 的时候，事实就是 P 串向后平移一位，恰好可以跳过从此处到上次不匹配的地方所有数，接着在上一次不匹配的地方又发生了不匹配的情况？

next数组：
计算next数组的时候，next[j]的值是在p串中，寻找一个值，使得以j为终点的某一段后缀与以这个值为终点的前缀完全相等，并且后缀与前缀要尽可能地长。举例：
i: 1 2 3 4 5 6 7 8 9
s: a b a b a b c b d
p: a b a b a b a b
p: # # a b a b a b a b
此时，i == 7, j + 1 == 7, j == 6;
next[j]的值，应该为让以j为终点的后缀a b a b与以这个值为终点的前缀a b a b相等，这时next[j] = 4.

对于p串，next数组的值为：
idx: 1 2 3 4 5 6 7 8
nex: 0 0 1 2 3 4 5 6
其中，当idx分别取1和2时，即j对应停留在1和2时，next值找不到满足条件的值，取0是为了退到起点让下一位i ++之后，和j + 1也就是 j == 1作比较。
idx == 3时，以下标3为后缀的a与以1为后缀的a相等。next[3] = 1;
idx == 4时，以下标4为后缀的a b与以2为后缀的a b相等。next[4] = 2;
idx == 5时，以下标5为后缀a b a与以3为后缀的a b a相等。next[5] = 3;
idx == 6时，以下标6为后缀a b a b与以4为后缀的a b a b相等。next[6] = 4;
idx == 7时，以下标7为后缀a b a b a与以5为后缀的a b a b a相等。next[7] = 5;
idx == 8时，以下标8为后缀a b a b a b与以6为后缀的a b a b a b相等。next[8] = 6;

#include <iostream>

using namespace std;

const int N = 100010, M = 1000010;

int n, m;
int ne[N];
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1;                        // 1

    for (int i = 2, j = 0; i <= n; i ++ )                   // 2
    {
        while (j && p[i] != p[j + 1]) j = ne[j];            // 3
        if (p[i] == p[j + 1]) j ++ ;                        // 4
        ne[i] = j;                                          // 5
    }

    for (int i = 1, j = 0; i <= m; i ++ )                   // 6
    {
        while (j && s[i] != p[j + 1]) j = ne[j];            // 7
        if (s[i] == p[j + 1]) j ++ ;                        // 8
        if (j == n)                                         // 9
        {
            printf("%d ", i - n);                           // 10
            j = ne[j];                                      // 11
        }
    }

    return 0;
}

###
待更新。