Pagini recente » Cod sursa (job #1837868) | Cod sursa (job #1058153) | Cod sursa (job #1760456) | Cod sursa (job #454476) | Cod sursa (job #171829)
Cod sursa(job #171829)
#include <stdio.h>
#include <string.h>
#define maxl 2000000
int i,j,x,p,q,n,nr,k,ok,m,baz;
int sol[1010];
char a[maxl],b[maxl];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
baz=26;
p=strlen(a)-1;
j=1;
nr=0;
for (i=p; i>=0; i--)
{
nr=(nr+(a[i]-97)*j)%666013;
j=(j*baz)%666013;
}
q=strlen(b)-1;
k=0;
j=1;
for (i=p; i>=0; i--)
{
k=(k+(b[i]-97)*j)%666013;
j=(j*baz)%666013;
}
x=j/baz;
ok=1;
for (i=0; i<=p; i++)
if (a[i]!=b[i])
{
ok=0;
break;
}
if (ok)
{
m++;
sol[m]=0;
}
for (i=p+1; i<=q; i++)
{
k=((k-(x*(b[i-p-1]-97)))*baz)%666013;
if (k<0) k+=666013;
k=(k+b[i]-97)%666013;
if (k<0) k+=666013;
if (k==nr)
{
ok=1;
for (j=0; j<=p; j++)
if (a[j]!=b[i-p+j]) {ok=0;break;}
if (ok)
{
m++;
sol[m]=i-p;
if (m>1000)
{
m=1000;
break;
}
}
}
}
printf("%d\n",m);
for (i=1; i<=m; i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}