Pagini recente » Cod sursa (job #1837840) | Monitorul de evaluare | Cod sursa (job #1042783) | Cod sursa (job #1990235) | Cod sursa (job #171852)
Cod sursa(job #171852)
#include <stdio.h>
#include <string.h>
#define maxl 2000010
int i,j,x,p,q,n,nr,k,ok,m,baz,prim;
int sol[1010];
int elem[125];
char a[maxl],b[maxl];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&a);
scanf("%s",&b);
baz=42;prim=666013;
j=0;
for (i='0'; i<='9'; i++)
elem[i]=++j;
for (i='a'; i<='z'; i++)
elem[i]=++j;
for (i='A'; i<='Z'; i++)
elem[i]=++j;
p=strlen(a)-1;
j=1;
nr=0;
for (i=p; i>=0; i--)
{
nr=(nr+elem[a[i]]*j)%prim;
j=(j*baz)%prim;
}
q=strlen(b)-1;
k=0;
j=1;
for (i=p; i>=0; i--)
{
k=(k+elem[b[i]]*j)%prim;
if (i==0) x=j;
j=(j*baz)%prim;
}
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*elem[b[i-p-1]]))%prim;
if (k<0) k+=prim;
k=(k*baz)%prim;
k=(k+elem[b[i]])%prim;
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)
break;
}
}
}
printf("%d\n",m);
if (m>1000) m=1000;
for (i=1; i<=m; i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}