Pagini recente » Cod sursa (job #150454) | Cod sursa (job #2203462) | Cod sursa (job #3000434) | Cod sursa (job #2367485) | Cod sursa (job #213674)
Cod sursa(job #213674)
#include<stdio.h>
#include<string.h>
long n,m,k,s[2000060],x[1005],i,l;
char a[2000060],b[2000060];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a);
gets(b);
n=strlen(a);
m=strlen(b);
for(i=n;i;--i)a[i]=a[i-1];
a[n+1]=0;
for(i=m;i;--i)b[i]=b[i-1];
b[m+1]=0;
k=0;
s[1]=0;
for(i=2;i<=n;++i)
{
while(k>0&&a[k+1]!=a[i])k=s[k];
if(a[k+1]==a[i])++k;
s[i]=k;
}
k=0;
for(i=1;i<=m;++i)
{
while(k>0&&a[k+1]!=b[i])k=s[k];
if(a[k+1]==b[i])++k;
if(k==n){k=s[n];++l;
if(l<=1000)x[l]=i-n;}
}
printf("%ld\n",l);
if(l>1000)l=1000;
for(i=1;i<=l;++i)
printf("%ld ",x[i]);
printf("\n");
return 0;
}