Pagini recente » Cod sursa (job #2508623) | Cod sursa (job #1910793) | Cod sursa (job #383234) | Cod sursa (job #662708) | Cod sursa (job #432137)
Cod sursa(job #432137)
//#include "stdafx.h"
#include<stdio.h>
#include<string.h>
#define NMAX 2000010
#define p 73
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];
hashx2=hashx2*p+x[i];
if (i!=0)
{
p1=p1*p;
p2=p2*p;
}
}
for (i=0;i<=n;i++)
{
hashy1=hashy1*p+y[i];
hashy2=hashy2*p+y[i];
}
if (hashx1==hashy1 && hashx2==hashy2)
rez[++rez[0]]=0;
for (i=n+1;i<=m;i++)
{
hashy1=(hashy1-y[i-n-1]*p1)*p+y[i];
hashy2=(hashy2-y[i-n-1]*p2)*p+y[i];
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;
}