Cod sursa(job #169275)

Utilizator DastasIonescu Vlad Dastas Data 1 aprilie 2008 15:25:01
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <cstdio>
#include <cstring>

const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;

const int mod1 = 100007;
const int mod2 = 100021;
const int p = 73;

FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");

char a[maxn];

int n, m;
char c[maxl];

int h1[mod1];
int h2[mod2];

int p1[maxl];
int p2[maxl];

int pow(int a, int b, int mod)
{
    int s = 1;

    for ( int i = 1; i <= b; ++i )
        s *= a,
        s %= mod;

    return s;
}

void getnr()
{
    int hash1 = 0, hash2 = 0;

    for ( int i = 0; i < n; ++i )
    {
        hash1 = (hash1 + p1[i] * c[i]) % mod1;
        hash2 = (hash2 + p2[i] * c[i]) % mod2;
    }

    ++h1[ hash1 ];
    ++h2[ hash2 ];
}

int cnt;
int main()
{
    fscanf(in, "%s", a);
    m = strlen(a);

    fscanf(in, "%s", c);
    n = strlen(c);

    for ( int i = 0; i < n; ++i )
        p1[i] = pow(p, n - i - 1, mod1),
        p2[i] = pow(p, n - i - 1, mod2);

    //for ( int i = 0; i < n; ++i )
    //    printf("%d %d\n", p1[i], p2[i]);

    getnr();

    while ( fscanf(in, "%s", c) == 1 )
        getnr();

    int hash1 = 0, hash2 = 0;
    for ( int i = 0; i < n; ++i )
    {
        hash1 = (hash1 + p1[i] * a[i]) % mod1;
        hash2 = (hash2 + p2[i] * a[i]) % mod2;
    }

    if ( h1[ hash1 ] && h2[ hash2 ] );
        ++cnt;

    for ( int i = n; i < m; ++i )
    {
        hash1 = ((hash1 - (a[i - n] * p1[0]) % mod1 + mod1) * p + a[i]) % mod1;
        hash2 = ((hash2 - (a[i - n] * p2[0]) % mod2 + mod2) * p + a[i]) % mod2;

        if ( h1[ hash1 ] && h2[ hash2 ] )
            ++cnt;
    }

    fprintf(out, "%d\n", cnt);

    return 0;
}