Pagini recente » Cod sursa (job #2986380) | Cod sursa (job #2937088) | Cod sursa (job #2522959) | Cod sursa (job #215586) | Cod sursa (job #153215)
Cod sursa(job #153215)
#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,i;
char match[MAXN];
int main()
{ freopen("strmatch.in", "rt", stdin);
freopen("strmatch.out", "wt", stdout);
scanf("%s %s", A, B);
NA=strlen(A);
NB=strlen(B);
P1=P2=1;
hashA1=hashA2=0;
for (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 (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)*P+B[i])%MOD1;
hash2=((hash2-(B[i-NA]*P2)%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&&Nr<1000;i++)
if (match[i])
Nr++,
printf("%d ", i);
printf("\n");
return 0;
}