#include <bits/stdc++.h> using namespace std; typedef unsigned long long ull; const int MAXN=1e6+5; const ull BASE=3; ull poww[MAXN]; ull hase1[MAXN]; ull hase2[MAXN]; int nxt[MAXN]; void init(){ poww[0]=1; for(int i=1;i<MAXN;++i){ poww[i]=poww[i-1]*BASE; } } int main(){ init(); string s1,s2; cin>>s1>>s2; int n=s1.size(); int m=s2.size(); hase1[0]=0; for(int i=0;i<n;i++){ hase1[i+1]=hase1[i]*BASE+(s1[i]-'A'+1); } hase2[0]=0; for(int i=0;i<m;i++){ hase2[i+1]=hase2[i]*BASE+(s2[i]-'A'+1); } ull base2=hase2[m]; for(int i=0;i<=n-m;i++){ ull base1=hase1[i+m]-hase1[i]*poww[m]; if(base1==base2){ cout<<i+1<<'\n'; } } nxt[0]=-1; for (int i=0;i<=m;i++) { int k=nxt[i]; while (k!=-1&&s2[i]!=s2[k]) { k=nxt[k]; } nxt[i+1]=k+1; } for(int i=1;i<=m;i++){ cout<<nxt[i]<<" "; } return 0; }