Pagini recente » Istoria paginii utilizator/amalia_ghica | Istoria paginii runda/cel_mai_mare_olimpicar_2019_oni2009_zi2 | Profil spatiisaudiacritice | Profil MihaelaCismaru | Cod sursa (job #432079)
Cod sursa(job #432079)
//#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]]=1;
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]);
for (i=1;i<=rez[0];i++)
printf("%d ",rez[i]);
printf("\n");
return 0;
}