https://www.luogu.com.cn/problem/P3375

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

char s1[1000010],s2[1000010];
int p[1000010];
int n , m;

int pre(){
	int j = 0;
	p[1] = 0;
	for(int i=1;i<m;i++){
		while(j>0&&s2[i+1]!=s2[j+1])
			j = p[j];
		if(s2[i+1]==s2[j+1])	j++;
		p[i+1] = j;
	}
}

int kmp(){
	pre();
	int j = 0;
	for(int i=0;i<n;i++){
		while(j>0&&s1[i+1]!=s2[j+1])
			j = p[j];
		if(s1[i+1]==s2[j+1])	j++;
		if(j == m){
			cout << i+1-m+1 << endl;
			j = p[j];
		}
	}
	for(int i=1;i<=m;i++){
		cout << p[i] << " ";
	}
}

int main(){
	cin >> s1+1 >> s2+1;
	n = strlen(s1+1);
	m = strlen(s2+1);
	kmp();
	return 0;
}