// KMP算法:构建next数组
vector<int> buildNext(const string& pattern) {
int n = pattern.size();
vector<int> next(n, 0);
int j = 0;
for (int i = 1; i < n; ++i) {
while (j > 0 && pattern[i] != pattern[j]) {
j = next[j - 1];
}
if (pattern[i] == pattern[j]) {
j++;
}
next[i] = j;
}
return next;
}
// KMP算法:在文本中查找模式串,返回所有匹配的起始位置
vector<int> kmpSearch(const string& text, const string& pattern) {
vector<int> result;
int n = text.size();
int m = pattern.size();
if (m == 0) return result;
vector<int> next = buildNext(pattern);
int j = 0;
for (int i = 0; i < n; ++i) {
while (j > 0 && text[i] != pattern[j]) {
j = next[j - 1];
}
if (text[i] == pattern[j]) {
j++;
}
if (j == m) {
result.push_back(i - m + 1);
j = next[j - 1];
}
}
return result;
}#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int i,j,n,m,next[1000005];string a,b;
int main(){
cin>>a>>b;
n=a.size();a='$'+a;
m=b.size();b='$'+b;
for(i=2,j=0;i<=m;i++){
while(j&&b[i]!=b[j+1])j=next[j];
if(b[i]==b[j+1])j++;
next[i]=j;
}
for(i=1,j=0;i<=n;i++){
while(j&&a[i]!=b[j+1])j=next[j];
if(a[i]==b[j+1])j++;
if(j==m){j=next[j];printf("%d\n",i-m+1);}
}
for(i=1;i<=m;i++)printf("%d ",next[i]);
}