Cod sursa(job #167894)

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

const int maxn = 10000003;
const int maxcuv = 23;

const int base = 3;
const int hmod = 666013;

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

//struct hash
//{
//    char cuv[maxcuv];
//    hash *next;
//};

char c[maxn];
//hash *h[hmod];
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;
}

char buf[maxcuv];
//
//void add(int x, char cuv[])
//{
//    hash *q = new hash;
//
//    int i;
//    for ( i = 0; cuv[i]; ++i )
//        q->cuv[i] = cuv[i];
//    q->cuv[i] = '\0';
//
//    q->next = h[x];
//    h[x] = q;
//}

int len;
void read()
{
    fscanf(in, "%s", c);

    int hh = 0;
    while ( fscanf(in, "%s", buf) == 1 )
    {
        // fa hashul cuvantului
        hh = 0;
        int i;
        for ( i = 0; buf[i]; ++i )
            hh = hh + (buf[i] * pow(base, i)),
            hh %= hmod;

        len = i;

        //add(hh, buf);
        ++h[ hh ];
        //printf("%d\n", hh);
    }
    //printf("\n\n");
}

void solve()
{
    int hh = 0;
    int cnt = 0;

    int n = strlen(c);
    for ( int i = 0; i < n - len + 1; ++i )
    {
        hh = 0;

        for ( int j = i; j < i + len; ++j )
            hh = hh + (c[j] * pow(base, j - i)),
            hh %= hmod;

        //printf("%d\n", hh);
        if ( h[ hh ] )
            ++cnt, h[ hh ] = 0;
    }

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

int main()
{
    read();

    solve();

	return 0;
}