Pagini recente » Cod sursa (job #2666744) | Cod sursa (job #1565090) | Cod sursa (job #117743) | Cod sursa (job #1449514) | Cod sursa (job #171863)
Cod sursa(job #171863)
#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);
while (k>prim) k-=prim;
if (i==0) x=j;
j=(j*baz);
while (j>prim) j-=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]]));
while (k>prim) k-=prim;
while (k<0) k+=prim;
k=(k*baz);
while (k>prim) k-=prim;
k=(k+elem[b[i]]);
while (k>prim) k-=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++;
if (m<=1000) sol[m]=i-p;
}
}
}
printf("%d\n",m);
if (m>1000) m=1000;
for (i=1; i<=m; i++)
printf("%d ",sol[i]);
printf("\n");
return 0;
}