Cod sursa(job #622090)

Utilizator vlad2901Vlad Berindei vlad2901 Data 17 octombrie 2011 13:35:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cstring>

#define MAXC 10000001
#define MAXCUV 25
#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)%MOD;

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

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

int hash_count(unsigned 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, ls;
    char cuv[MAXCUV];
    unsigned key = 0;
    unsigned r;

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

    fgets(s, MAXC, stdin);
    fgets(cuv, MAXCUV, stdin);
    l = strlen(cuv);
    do
    {
        if(cuv[l-1] == '\n')
        {
            cuv[l-1] = '\0';
        }
        hash_insert(cuv);
    } while(fgets(cuv, MAXCUV, stdin));

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

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

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


    return 0;
}