#include<iostream>
#include<cstring>
#include<fstream>
#define N 2000005
#define nr_chares 256
using namespace std;
char pat[N],text[N];
void preprocess_strong_suffix(int *shift,int *bpos,char *pat,int m)
{
int i=m,j=m+1;
bpos[i]=j;
while(i>0)
{
while(j<=m && pat[i-1]!=pat[j-1])
{
if(shift[j]==0)
shift[j]=j-i;
//shift[m]=1 prin constructie
j=bpos[j];
}
i--;
j--;
//relatia de recurenta
bpos[i]=j;
}
}
void preprocess_case2(int *shift,int *bpos,char *pat,int m)
{
int i,j=bpos[0];
for(i=0;i<=m;i++)
{
if(shift[i]==0)
shift[i]=j;
if(i==j)
j=bpos[j];
}
}
int min(int a,int b)
{
if(a<b)
return a;
else
return b;
}
int max(int a,int b)
{
return a+b-min(a,b);
}
void bad_char_heuristic(char *pat,int size,int bad[nr_chares])
{
int i;
for(i=0;i<nr_chares;i++)
bad[i]=-1;
for(i=0;i<size;i++)
bad[(int)pat[i]]=i;
}
void boyer_moore(char *pat,char *text)
{
int n=strlen(text),m=strlen(pat);
//avem nevoie si de terminatorul de sir pentru cazul 3, cand
int s=0,i,j,bpos[m+1],shift[m+1],nrap=0,v[1024],bad[nr_chares];
for(i=0;i<m+1;i++)
shift[i]=0;
preprocess_strong_suffix(shift,bpos,pat,m);
//for(i=0;i<m+1;i++) cout<<bpos[i]<<' ';
preprocess_case2(shift,bpos,pat,m);
//for(i=0;i<m+1;i++) cout<<shift[i]<<' ';
bad_char_heuristic(pat,m,bad);
while(s<=n-m)
{
j=m-1;
while(j>=0 && pat[j]==text[s+j])
j--;
if(j==-1)
{
if(nrap<1000) v[++nrap]=s;
else nrap++;
s+=max(shift[0],m-bad[(int)text[s+m]]);
}
else
s+=max(shift[j+1],j-bad[(int)text[s+j]]);
}
ofstream fout("strmatch.out");
fout<<nrap<<'\n';
for(i=1;i<=min(1000,nrap);i++)
fout<<v[i]<<' ';
fout.close();
}
int main()
{
ifstream fin("strmatch.in");
fin.getline(pat,sizeof(pat));
fin.getline(text,sizeof(text));
fin.close();
boyer_moore(pat,text);
}