KMP模板求条

KMP

#include <bits/stdc++.h>
#define int __int128_t
#define range(VAR, START, END, STEP) for (int(VAR) = (START); (STEP) * (VAR) <= (STEP) * (END); (VAR) += (STEP))
#define loop(END) for (int i = 1; i <= (END); i++)
#define MAXN (signed)(1e6 + 10)
#define pr() putchar('\n')
#define ps() putchar(' ')
#define m(x) memset(x, 0, sizeof(x))
using namespace std;
int read()
{
    int nm = 0, zf = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar())
        if (c == '-')
            zf = -1;
    for (; isdigit(c); c = getchar())
        nm = nm * 10 + (c - '0');
    return nm * zf;
}
void write(int x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x >= 10)
        write(x / 10);
    putchar(x % 10 + '0');
}
char str1[MAXN], str2[MAXN];
int next_element[MAXN];
signed main()
{
    cin >> (str1 + 1);
    cin >> (str2 + 1);
    int n = strlen(str1 + 1), m = strlen(str2 + 1);

    int i = 1, len = 0;
    next_element[1] = 1;
    range(i, 2, m, 1)
    {
        while (len && str2[len + 1] != str2[i])
            len = next_element[len - 1];
        if (str2[len + 1] == str2[i])
            len++;
        next_element[i] = len;
    }
    len = 0;
    range(i, 1, n, 1)
    {
        while (len && str1[i] != str2[len + 1])
        {
            len = next_element[len];
        }

        if (str1[i] == str2[len + 1])
            len++;
        if (len == m)
        {
            len = next_element[len];
            write(i - m + 1);
            pr();
        }
    }
    range(i, 1, m, 1)
    {
        write(next_element[i]);
        ps();
    }
    return EXIT_SUCCESS;
}