Pagini recente » Cod sursa (job #2922283) | Cod sursa (job #1408482) | Cod sursa (job #3269075) | Cod sursa (job #3164741) | Cod sursa (job #171903)
Cod sursa(job #171903)
#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];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
// scanf("%s",b);
baz=42;prim=75000001;
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+1LL*elem[a[i]]*j)%prim;
j=(1LL*j*baz)%prim;
}
scanf("%s",a);
q=strlen(a)-1;
k=0;
j=1;
for (i=p; i>=0; i--)
{
k=(k+1LL*elem[a[i]]*j)%prim;
if (i==0) x=j;
j=(1LL*j*baz)%prim;
}
if (k==nr)
{
m++;
sol[m]=0;
}
for (i=p+1; i<=q; i++)
{
k=(k-(1LL*x*elem[a[i-p-1]]))%prim;
if (k<0) k+=prim;
k =(1LL * k * baz + elem[a[i]]) % prim;
if (k==nr)
{
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;
}