KMP

思考方式

1. 暴力做法
2. 如何去优化

n e x t [ i ] next[i] next[i] 的含义：以 i i i 为终点的后缀和从 1 1 1 开始的前缀相等并且后缀的长度最长

e . g .   n e x t [ i ] = j e.g. \ next[i]=j e.g. next[i]=j 表示的是 p [ 1 → j ] p[1\to j] p[1→j] 这一段和 p [ ( i − j + 1 ) → j ] p[(i-j+1) \to j] p[(i−j+1)→j] 这段相等（如下图，红颜色段被绿颜色标出的两部分相等

Code

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
//求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i++) {
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j++;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i++) {
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j++;
    if (j == m) {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}