Cod sursa(job #631164)

Utilizator cremarencodianaCremarenco Diana cremarencodiana Data 7 noiembrie 2011 10:02:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include <stdio.h>
#include <string.h>
#define MAXN 2000001
#define P 73
char a[MAXN], b[MAXN];
int n, m;
int hash11, hash12, P1, P2;
char match[MAXN]; 
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b); 
n = strlen(a);
m = strlen(b);
 
P1 = P2 = 1;
hash11 = hash12 = 0;
for (int i = 0; i < n; i++)
{
    hash11 = (hash11 * P + a[i]) % 100007;
    hash12 = (hash12 * P + a[i]) % 100021;
    if (i != 0)
       P1 = (P1 * P) % 100007,
       P2 = (P2 * P) % 100021;
}

if (n > m)
{
    printf("0\n");
    return 0;

}
int hash21 = 0, hash22 = 0;
for (int i = 0; i < n; i++)
    hash21 = (hash21 * P + b[i]) % 100007,
    hash22 = (hash22 * P + b[i]) % 100021;
int nr = 0;
if (hash21 == hash11 && hash22 == hash12)
    match[0] = 1, nr++;
 
for (int i = n; i < m; i++)
{
   hash21 = ((hash21 - (b[i - n] * P1) % 100007 + 100007) * P + b[i]) % 100007;
   hash22 = ((hash22 - (b[i - n] * P2) % 100021 + 100021) * P + b[i]) % 100021;
    if (hash21 == hash11 && hash22 == hash12)
        match[ i - n + 1 ] = 1, nr++;
}
printf("%d\n", nr);
nr = 0;
for (int i = 0; i < m && nr < 1000; i++)
    if (match[i])
       nr++,
printf("%d ", i);
printf("\n");

return 0;
}