[AcWing面向模型编程]kmp

题目：831. KMP字符串

分析：

听y总讲了一遍kmp，感觉理解的还不错，应该可以默写了。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef __int128 lll;
#define print(i) cout << "debug: " << i << endl
#define close() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define mem(a, b) memset(a, b, sizeof(a))
const ll mod = 1e9 + 7;
const int maxn = 2e6;
const int inf = 0x3f3f3f3f;
int n, m;
char model[maxn], now[maxn];
int nex[maxn];

void getnex()
{
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && model[j + 1] != model[i]) j = nex[j];
        if (model[j + 1] == model[i]) j++;
        nex[i] = j;
    }
}
// now-m
// model-n
void kmp()
{
    getnex();
    for (int i = 1, j = 0; i <= m; i++)
    {
        while (j && model[j + 1] != now[i]) j = nex[j];
        if (model[j + 1] == now[i]) j++;
        if (j == n) cout << i - n << ' ', j = nex[j];
    }
}

int main()
{
    cin >> n >> model + 1 >> m >> now + 1;
    kmp();
}