Cod sursa(job #165650)
#include<stdio.h>
using namespace std;
char a[2000002], b[2000002];
int m, n, lim, r[1024], pi[2000002];
void prefix(){
int i, k;
pi[1]=0;
k=0;
for(i=2;i<=m;i++){
while(k && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
k++;
pi[k]=k;
}
}
void match(){
int i, k;
k=0;
for(i=1;i<=n;i++){
while(k && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
k++;
if(k==m)
{
lim++;
k=pi[k];
if(lim<1001) r[lim]=i-m+1;
}
}
}
int main(){
int i;
freopen("strmatch.in","r", stdin);
fgets(a, sizeof(a), stdin);
fgets(b, sizeof(b), stdin);
fclose(stdin);
for(n=0;b[n]<='Z'&&b[n]>='A'||b[n]<='z'&&b[n]>='a'||b[n]<='9'&&b[n]>='0';n++);
for(m=0;a[m]<='Z'&&a[m]>='A'||a[m]<='z'&&a[m]>='a'||a[m]<='9'&&a[m]>='0';m++);
for(i=m;i>0;i--)
a[i]=a[i-1];
a[m+1]=0;
for(i=n;i>0;i--)
b[i]=b[i-1];
b[n+1]=0;
prefix();
match();
freopen("strmatch.out","w",stdout);
printf("%d\n",lim);
int min;
min=(1000<lim)?1001:(lim+1);
for(i=1;i<min;i++)
printf("%d ",r[i]);
fclose(stdout);
return 0;
}