Pagini recente » Cod sursa (job #442272) | Cod sursa (job #552215) | Cod sursa (job #1246971) | Cod sursa (job #2292786) | Cod sursa (job #432090)
Cod sursa(job #432090)
//#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#define NMAX 2000010
#define p 73
#define mod1 100007
#define mod2 100021
char x[NMAX],y[NMAX];
int n,m,p1,p2,i,j,rez[NMAX],hashx1,hashx2,hashy1,hashy2;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",x,y);
n=strlen(x)-1;
m=strlen(y)-1;
if (n>m)
{
printf("0\n");
return 0;
}
p1=p2=1;
for (i=0;i<=n;i++)
{
hashx1=(hashx1*p+x[i])% mod1;
hashx2=(hashx2*p+x[i])% mod2;
if (i!=0)
{
p1=(p1*p)%mod1;
p2=(p2*p)%mod2;
}
}
for (i=0;i<=n;i++)
{
hashy1=(hashy1*p+y[i])%mod1;
hashy2=(hashy2*p+y[i])%mod2;
}
if (hashx1==hashy1 && hashx2==hashy2)
rez[++rez[0]]=0;
for (i=n+1;i<=m;i++)
{
hashy1=((hashy1-(y[i-n-1]*p1)%mod1+mod1)*p+y[i])%mod1;
hashy2=((hashy2-(y[i-n-1]*p2)%mod2+mod2)*p+y[i])%mod2;
if (hashx1==hashy1 && hashx2==hashy2)
rez[++rez[0]]=i-n;
}
printf("%d\n",rez[0]);
if (rez[0]>1000)
rez[0]=1000;
for (i=1;i<=rez[0];i++)
printf("%d ",rez[i]);
printf("\n");
return 0;
}