Cod sursa(job #615727)

Utilizator vlad2901Vlad Berindei vlad2901 Data 10 octombrie 2011 18:14:05
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <cstdio>
#include <cstring>

#define MAXC 10000001
#define MOD 666013

char s[MAXC];

struct list
{
    long long key;
    list *next;
} *h[MOD];

unsigned cod(char *cuv)
{
    unsigned c = 0;
    int i;
    for(i=0;i<strlen(cuv);++i)
    {
        c = c * 3 + cuv[i] - 'a';
    }
    return c;
}

void hash_insert(char *cuv)
{
   list *node;
   unsigned key = cod(cuv);

   for(node=h[key%MOD];node;node=node->next)
   {
       if(node->key == key)
       {
           return;
       }
   }

   node = new list;
   node->key = key;
   node->next = h[key%MOD];
   h[key%MOD] = node;
}

int hash_count(int key)
{
    list *node;
    int nr = 0;

    for(node = h[key%MOD]; node; node=node->next)
    {
        if(node->key == key)
        {
            ++nr;
        }
    }
    return nr;
}

int main()
{
    int i, l, sol = 0;
    char cuv[20];
    unsigned key = 0;
    unsigned r;

    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);

    fgets(s, MAXC, stdin);

    while(fgets(cuv, 25, stdin))
    {
        if(cuv[strlen(cuv)-1] == '\n')
        {
            cuv[strlen(cuv)-1] = '\0';
        }
        hash_insert(cuv);
    }

    l = strlen(cuv);
    r = 1;
    for(i=l-1;i>=0;--i)
    {
        key = key * 3 + s[i] - 'a';
        r *= 3;
    }
    r /= 3;
    sol += hash_count(key);

    for(i=1;i<strlen(s);++i)
    {
        key %= r;
        key = key * 3 + s[i] - 'a';
        sol += hash_count(key);
    }

    printf("%d\n", sol);


    return 0;
}