Pagini recente » Cod sursa (job #3191473) | Cod sursa (job #2612819) | Cod sursa (job #645626) | Cod sursa (job #751188) | Cod sursa (job #153041)
Cod sursa(job #153041)
#include <stdio.h>
#include <string.h>
#define NMAX 2000050
#define P 73
#define MOD1 100023
#define MOD2 100007
char a[NMAX], b[NMAX];
long n, m;
long ap[1010], h;
long na, nb;
long ha1, ha2, hb1, hb2;
long nr;
long p1, p2;
int main()
{
int i;
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s", a+1);
scanf("%s", b+1);
na = strlen(a+1);
nb = strlen(b+1);
if(na > nb)
{
printf("0");
return 0;
}
p1 = p2 = 1;
for(i = 1; i <= na; ++i)
{
ha1 = (ha1*P + a[i]) % MOD1;
ha2 = (ha2*P + a[i]) % MOD2;
hb1 = (hb1*P + b[i]) % MOD1;
hb2 = (hb2*P + b[i]) % MOD2;
if(i != 1)
p1 = (p1*P) % MOD1,
p2 = (p2*P) % MOD2;
}
if(ha1 == hb1 && ha2 == hb2)
ap[++h] = 0;
for(i = na+1; i <= nb; ++i)
{
hb1 = ( (hb1 - (p1*b[i-na]) % MOD1 + MOD1) * P + b[i] ) % MOD1;
hb2 = ( (hb2 - (p2*b[i-na]) % MOD2 + MOD2) * P + b[i] ) % MOD2;
if(ha1 == hb1 && ha2 == hb2)
{
if(h < 1000)
ap[++h] = i-na;
else
++h;
}
}
printf("%ld\n", h);
for(i = 1; i <= 1000 && i <= h; ++i)
printf("%ld ", ap[i]);
return 0;
}