Pagini recente » Cod sursa (job #2704400) | Cod sursa (job #3255448) | Cod sursa (job #461390) | Cod sursa (job #2936866) | Cod sursa (job #155670)
Cod sursa(job #155670)
#include<stdio.h>
#include<string.h>
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
char A[MAXN], B[MAXN];
int NA, NB;
int hashA1, hashA2, P1, P2;
char match[MAXN];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s %s",A,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;
}
}
if (NA>NB)
{
printf("0\n");
return 0;
}
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 (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 (i=0;i<NB;i++)
if (match[i])
{
Nr++;
printf("%d ",i);
}
printf("\n");
return 0;
}