Cod sursa(job #106947)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 19 noiembrie 2007 00:18:39
Problema Abc2 Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define S ((1<<20)-1)

int V[S+10], Nr, ncol;
unsigned int Val[S];
char ss[10000002], ss2[50002];

int main()
{
        int i, t, l, n, cst;
        unsigned int p, pp, hash, val;

        srand(time(0));

        freopen("abc2.in", "r", stdin);
        gets(ss);
        n = strlen(ss);

        cst = 'a';

        while (scanf(" %s", ss2)==1)
        {
                l = strlen(ss2);
                val = 0;
                pp = 1;
                for (i = 0; i < l; i++) val = val+(ss2[i]-cst)*pp, pp *= 3;
                hash = val&S;
                t = 0;
                while ((V[hash]>0)&&(Val[hash]!=val)) hash = (hash+(++t))&S;
                V[hash] = 1; Val[hash] = val;
        }

        cst = 'a';
        val = 0; pp = 1;
        for (i = 0; i < l; i++) val = val+(ss[i]-cst)*pp, pp *= 3;
        p = pp/3;
        hash = val&S; Nr+=V[hash];

        for (i = l; i <= n; i++)
        {
                val = (val/3)+(ss[i]-cst)*p;
                hash = val&S;
                for (t=0; ((V[hash]>0)&&(Val[hash]!=val)) ;hash = (hash+(++t))&S);
                Nr += V[hash];
        }

        freopen("abc2.out", "w", stdout);
        printf("%d\n", Nr);

        return 0;
        
}