KMP板子

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using i128=__int128;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using db = double;
using ldb = long double;
#define F first
#define S second
vector<int> kmp(string s) {
    int n = s.size();
    vector<int> f(n);
    for (int i = 1, j = 0; i < n; i++) {
        while (j && s[i] != s[j]) j = f[j-1];
        if (s[i] == s[j]) j++;
        f[i] = j;
    }
    return f;
}

void solve(){
    string a,b;cin>>a>>b;
    vector<int> next=kmp(b);
    int n=a.size(),m=b.size(),ans=-1;
    int j=0;
    for(int i=0;i<n;i++){
        while(j&&a[i]!=b[j]) j=next[j-1];
        if(a[i]==b[j]) j++;
        if(j==m){
            cout<<i+2-m<<"\n";
        }
    }
    for(int i=0;i<m;i++){
        cout<<next[i]<<" ";
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--) solve();
    return 0;
}