KMP

简介

对比朴素枚举，KMP 的思想是当匹配出现不一样的字符时，根据模式串当前子串的最大相同前后缀，将模式串的指针回退到最大相同前缀的末尾而非模式串的开头，从而优化时间复杂度。

记录子串最大相同前后缀长度的数组为 $next_i$。下图展示了 $next_i$ 的求解过程。

Code

模板传送门

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

string s, t;
int lens, lent, nxt[N];

void getNext()
{
    for (int i = 1, j = 0; i < lent; i++) {
        while (j > 0 && t[i] != t[j])
            j = nxt[j - 1];
        if (t[j] == t[i]) ++j;
        nxt[i] = j;
    }
}

void KMP()
{
    int j = 0;
    for (int i = 0; i < lens; i++) {
        while (j > 0 && s[i] != t[j])
            j = nxt[j - 1];
        if (s[i] == t[j]) j++;
        if (j == lent) {
            printf("%d\n", i - lent + 2);
            j = nxt[j - 1];
        }
    }
}

int main()
{
    cin >> s >> t;
    lens = s.size(); lent = t.size();
    getNext();
    KMP();
    for (int i = 0; i < lent; i++)
        printf("%d ", nxt[i]);
    return 0;
}