Cod sursa(job #167896)

Utilizator DastasIonescu Vlad Dastas Data 30 martie 2008 12:48:15
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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 )
    {
        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 ];
    }
}

int exist(int hh, char cuv[])
{
    hash *q = h[ hh ];

    while ( q )
        if ( strcmp(q->cuv, cuv) == 0 )
            return 1;

    return 0;
}

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

    int n = strlen(c);
    char cuv[maxcuv];

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

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

        if ( exist(hh, cuv) )
            ++cnt, h[ hh ] = NULL;
    }

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

int main()
{
    read();

    solve();

	return 0;
}