Cod sursa(job #167919)

Utilizator DastasIonescu Vlad Dastas Data 30 martie 2008 13:13:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <cstring>

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

const int hmod = 1<<20;
const int base = 3;

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

char a[maxn];

int n, m;
char c[maxl];

int h[hmod];

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

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

    return s;
}

int getnr()
{
    unsigned int r = 0;

    int k = n - 1;
    for ( int i = 0; i < n; ++i )
    {
        //r = (r + (c[i] - 'a')*pow(base, k--)) % hmod;
        r += c[i];
        r += ( r << 10 );
        r ^= ( r >> 6 );
    }

    r += ( r << 3 );
    r ^= ( r >> 11 );
    r += ( r << 15 );

    return r & (hmod - 1);
}

int check(int x, int y)
{
    unsigned int r = 0;

    int k = n - 1;
    for ( int i = x; i < y; ++i )
    {
        //r = (r + (a[i] - 'a')*pow(base, k--)) % hmod;

        r += a[i];
        r += ( r << 10 );
        r ^= ( r >> 6 );
    }

    r += ( r << 3 );
    r ^= ( r >> 11 );
    r += ( r << 15 );

    return r & (hmod - 1);
}

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

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

    ++h[ getnr() ];

    while ( fscanf(in, "%s", c) == 1 )
        ++h[ getnr() ];

    for ( int i = 0; i < m; ++i )
    {
        int k = i + n;
        if ( k > m )
            break;

        if ( h[ check(i, k) ] )
            ++cnt;
    }

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

    return 0;
}