Cod sursa(job #102977)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 14 noiembrie 2007 20:31:48
Problema Abc2 Scor 0
Compilator c Status done
Runda Happy Coding 2007 Marime 1.35 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define S ((1<<20)-1)

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

int main()
{
        int i, t, l, n, cst;
        long long 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;
                t = 0;
                while ((V[hash]>0)&&(Val[hash]!=val))
                      hash = (hash+(++t))&S, ncol++;
                Nr += V[hash];
        }

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

        return 0;
        
}