Pagini recente » Cod sursa (job #1697268) | Cod sursa (job #2479566) | Cod sursa (job #935641) | Cod sursa (job #3198649) | Cod sursa (job #1616979)
#include<cstdio>
#include<cstring>
const int NMAX=2000010;
char A[NMAX],B[NMAX];
const int MOD1=666013,MOD2=100021;
int rasp[NMAX],nr_rasp;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(A+1);
gets(B+1);
int n=strlen(A+1),m=strlen(B+1);
int Ahash1=0,Ahash2=0;
int put1=1,put2=1;
for(int i=1;i<=n;i++)
{
Ahash1=(73*Ahash1+A[i])%MOD1;
Ahash2=(73*Ahash2+A[i])%MOD2;
if(i>1)
{
put1*=73;
put1%=MOD1;
put2*=73;
put2%=MOD2;
}
}
//printf("%d\n%d\n",Ahash1,Ahash2);
int Bhash1=0,Bhash2=0;
for(int i=1;i<=n;i++)
{
Bhash1=(73*Bhash1+B[i])%MOD1;
Bhash2=(73*Bhash2+B[i])%MOD2;
}
//printf("%d\n%d\n",Bhash1,Bhash2);
if(Bhash1==Ahash1 && Bhash2==Ahash2)
{
if(nr_rasp<1000)
rasp[++nr_rasp]=0;
else
++nr_rasp;
}
for(int i=n+1;i<=m;i++)
{
Bhash1=((Bhash1-(put1*B[i-n])%MOD1+MOD1)*73+B[i])%MOD1;
Bhash2=((Bhash2-(put2*B[i-n])%MOD2+MOD2)*73+B[i])%MOD2;
if(Bhash1==Ahash1 && Bhash2==Ahash2)
{
if(nr_rasp<1000)
rasp[++nr_rasp]=i-n;
else
++nr_rasp;
}
}
printf("%d\n",nr_rasp);
for(int i=1;i<=nr_rasp && i<=1000;i++)
printf("%d ",rasp[i]);
return 0;
}