Cod sursa(job #167904)

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

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

const int hmod = 666013;

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 x, int y)
{
    if ( y == 0 )
        return 1;

    if ( y == 1 )
        return x % hmod;

    long long t = pow(x, y >> 1);

    if ( (y & 1) )
        return (long long)(((long long)(t * t) % hmod) * x) % hmod;

    return (long long)(t * t) % hmod;
}

int getnr()
{
    int r = 0;

    int k = n - 1;
    for ( int i = 0; i < n; ++i )
        r = (r + (c[i]-'a')*pow(3,k--)) % hmod;

    return r;
}

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

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

    return r;
}

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

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

    ++h[ getnr() ];
   // printf("%d\n", getnr());

    while ( fscanf(in, "%s", c) == 1 )
        ++h[ getnr() ];//, printf("%d\n", getnr());;

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

        //printf("%d\n", check(i, k));
        if ( h[ check(i, k) ] )
            ++cnt;
    }

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

    return 0;
}