字符串

KMP

const int N = 1e6 + 5;
int n, m;
int nxt[N]; // t串前缀的border长度
char s[N], t[N];

int main()
{
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    for (int i = 2; i <= m; i++)
    {
        int j = nxt[i - 1];
        while (j > 0 && t[i] != t[j + 1])
            j = nxt[j];
        if (t[i] == t[j + 1])
            nxt[i] = j + 1;
    }
    for (int i = 1, j = 0; i <= n; i++)
    {
        while (j > 0 && s[i] != t[j + 1])
            j = nxt[j];
        if (s[i] == t[j + 1])
            j++;
        if (j == m)
            printf("%d\n", i - m + 1);
    }
    for (int i = 1; i <= m; i++)
        printf("%d%c", nxt[i], " \n"[i == m]);
    return 0;
}