Pagini recente » Cod sursa (job #919560) | Cod sursa (job #1517749) | Cod sursa (job #283362) | Cod sursa (job #2536866) | Cod sursa (job #1009690)
#include<stdio.h>
#include<string.h>
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[2000001], B[2000001],match[2000001];
int hashA1, hashA2, hash1, hash2, nr, P1=1, P2=1;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",A,B);
int NA = strlen(A);
int NB = strlen(B);
if(NA>NB)
{
printf("%d",0);
return 0;
}
for(int i=0;i<NA;++i)
{
hashA1 = (hashA1*P+A[i])%MOD1;
hashA2 = (hashA2*P+A[i])%MOD2;
if(i)
{
P1=(P1*P)%MOD1;
P2=(P2*P)%MOD2;
}
}
for(int i=0;i<NA;++i)
{
hash1 = (hash1*P + B[i])%MOD1;
hash2 = (hash2*P + B[i])%MOD2;
}
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);
for(int i=0;i<NB;++i)
{
if(nr)
{
if(match[i]==1)
{
printf("%d ",i);
--nr;
}
}
else
break;
}
return 0;
}