LP3375.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int nxt[N];
string s1, s2;

signed main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> s1 >> s2;
    int n = s1.size(), m = s2.size();
    s1 = ' ' + s1;
    s2 = ' ' + s2;

    for (int i = 2; i <= m; i++) {
        nxt[i] = nxt[i-1];
        while (nxt[i] && s2[nxt[i]+1] != s2[i]) nxt[i] = nxt[nxt[i]];
        nxt[i] += s2[nxt[i]+1] == s2[i];
    }

    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j && s1[i] != s2[j+1]) j = nxt[j];
        if (s1[i] == s2[j+1]) j++;
        if (j == m) {
            j = nxt[j];
            cout << i-m+1 << '\n';
            continue;
        }
    }

    for (int i = 1; i <= m; i++) cout << nxt[i] << " \n"[i == m];

    return 0;
}