传送门

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#define re register

using namespace std;

const int maxn = 1000005;

inline long long read() {

	char ch = getchar();

	long long f = 1 , x = 0;

	while(ch > '9' || ch < '0') {if(ch == '-') f = -1 ;ch = getchar();}

	while(ch >= '0' && ch <= '9') {x = (x << 1) + ( x << 3) + ch - '0';ch = getchar();}

	return x * f;

}

char s1[maxn],s2[maxn];

int len1,len2;

int nxt[maxn];

//用于记录当匹配到模式串的第 i 位之后失配,该跳转到模式串的哪个位置

int main(){

	cin >> s1 + 1 >> s2 + 1 ;

	len1 = strlen(s1 + 1) , len2 = strlen(s2 + 1);

	nxt[0] = nxt[1] = 0;

	int j ;//j可以看做表示当前已经匹配完的模式串的最后一位的位置

	for(re int i = 2 ; i <= len2 ; ++i) {

		while(j && s2[i] != s2[j + 1])  j = nxt[j];

		//如果失配 ，那么就不断向回跳，直到可以继续匹配

		if(s2[j + 1] == s2[i])  j++;

		//如果匹配成功，那么对应的模式串位置++

		nxt[i] = j ;

	}

	j = 0;

	for(re int i = 1 ; i <= len1 ; ++i) {

		while(j && s2[j + 1] != s1[i]) j = nxt[j];

		//此处判断j是否为0的原因在于，如果回跳到第一个字符就不 用再回跳

		if(s2[j + 1] == s1[i])  j++ ;

		if(j == len2) {

			printf("%d\n",i - len2 + 1) ;

			j = nxt[j];

		}

	}

	for(re int i = 1 ; i <= len2 ; ++i)

		printf("%d " , nxt[i]);

	return 0;

}