Cod sursa(job #622421)

Utilizator vlad2901Vlad Berindei vlad2901 Data 17 octombrie 2011 22:18:27
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <cstdio>
#include <cstring>

#define MAXC 10000001
#define MAXCUV 22
#define MOD 666013

char s[MAXC];
int l;

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

unsigned cod(char *cuv)
{
    unsigned c = 0;
    int i;
    for(i=0;i<l;++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(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, sol = 0, last, 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);
    if(cuv[l-1] == '\n')
    {
        cuv[l-1] = '\0';
        --l;
    }

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

    }

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

    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;
}