Pagini recente » Cod sursa (job #155630) | Cod sursa (job #1145464) | Cod sursa (job #2758769) | Cod sursa (job #1017843) | Cod sursa (job #493492)
Cod sursa(job #493492)
#include <stdio.h>
#include <string.h>
#define DIM 2000002
#define LIMIT 1000
#define BZ 73
#define MOD1 100002
#define MOD2 100067
int P1, P2;
char A[DIM], B[DIM];
int NA, NB, hashA1, hashA2, hashB1, hashB2;
int match[LIMIT], NR;
void cit ()
{
scanf ("%s%s", A, B);
NA = strlen (A);
NB = strlen (B);
}
void hash ()
{
P1 = P2 = 1;
for (int i = 0; i < NA; ++i)
{
hashA1 = (hashA1 * BZ + A[i]) % MOD1,
hashA2 = (hashA2 * BZ + A[i]) % MOD2;
hashB1 = (hashB1 * BZ + B[i]) % MOD1,
hashB2 = (hashB2 * BZ + B[i]) % MOD2;
if (i != 0)
{
P1 = (P1 * BZ) % MOD1;
P2 = (P2 * BZ) % MOD2;
}
}
if (hashA1 == hashB1 && hashA2 == hashB2)
match[NR++] = 0;
for (int i = NA; i < NB; ++i)
{
hashB1 = ((hashB1 - (B[i - NA] * P1) % MOD1 + MOD1) * BZ + B[i]) % MOD1,
hashB2 = ((hashB2 - (B[i - NA] * P2) % MOD2 + MOD2) * BZ + B[i]) % MOD2;
if (hashA1 == hashB1 && hashA2 == hashB2)
{
if (NR < LIMIT)
match[NR] = i - NA + 1;
++NR;
}
}
}
void afs ()
{
printf ("%d\n", NR);
if (NR > LIMIT) NR = LIMIT;
for (int i = 0; i < NR; ++i)
printf ("%d ", match[i]);
}
int main ()
{
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
cit ();
hash ();
afs ();
return 0;
}