Pagini recente » Cod sursa (job #508651) | Cod sursa (job #1177859) | Cod sursa (job #228808) | Cod sursa (job #1754800) | Cod sursa (job #2189630)
#include <stdio.h>
#include <string.h>
#define NMAX 2000001
#define p 29
#define MOD1 120997
#define MOD2 121271
char a[NMAX], b[NMAX];
int na, nb;
int hasha1, hasha2, p1, p2;
char match[NMAX];
int main()
{
freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
gets(a);
gets(b);
na=strlen(a);
nb=strlen(b);
p1=p2=1;
hasha1=hasha2=0;
for(int i=0;i<na;i++)
{
hasha1=(hasha1*p+a[i])%MOD1;
hasha2=(hasha2*p+a[i])%MOD2;
if(i!=0)
{
p1=(p1*p)%MOD1,
p2=(p2*p)%MOD2;
}
}
int hash1=0,hash2=0;
for(int i=0;i<na;i++)
{hash1=(hash1*p+b[i])%MOD1;hash2=(hash2*p+b[i])%MOD2;}
int nr=0;
if(hash1==hasha1&&hash2==hasha2)
{match[0]=1;nr++;}
for(int i=na;i<nb;i++)
{
hash1=((hash1-(b[i-na]*p1)%MOD1+MOD1)*p+b[i])%MOD1;
hash2=((hash2-(b[i-na]*p2)%MOD2+MOD2)*p+b[i])%MOD2;
if(hash1==hasha1&&hash2==hasha2)
{match[i-na+1]=1;nr++;}
}
printf("%d\n",nr);
nr=0;
for(int i=0;i<nb&&nr<1000;i++)
if(match[i])
{nr++;printf("%d ",i);}
printf("\n");
return 0;
}