Cod sursa(job #1492953)

Utilizator felixiPuscasu Felix felixi Data 28 septembrie 2015 14:44:19
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

const int MOD = 666013;
const int MAX_WORDS = 50000;
const int MAX_LEN = 10000000;
const int MAX_WORDLEN = 20;
const int NIL = -1;
const int POW3[] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467 };

char a[MAX_LEN + 1];
char word[MAX_WORDLEN + 1];

ifstream in(                     "abc2.in"                         );
ofstream out(                    "abc2.out"                        );

struct cell
{
    unsigned key;
    int next;
};

cell l[MAX_WORDS];
int ptr;
int H[MOD];

inline void hashInsert(const unsigned &key)
{
    l[ptr].key = key;
    l[ptr].next = H[key % MOD];
    H[key  % MOD] = ptr++;
}

inline bool hashFind(const unsigned &key)
{
    int i = H[key % MOD];
    while ((i != NIL) && (l[i].key != key))
        i = l[i].next;
    return i != NIL;
}

int main()
{

    int n, i;
    int res;
    unsigned h;

    in >> a;
    memset(H, NIL, sizeof(H));
    while (in >> word)
    {
        h = 0;
        for (char *p = word; *p; p++)
            h = ((h << 1) + h) + (*p - 'a');
        if (!hashFind(h))
            hashInsert(h);
    }
    in.close();

    n = strlen(word);

    i = 0;
    h = 0;
    res = 0;

    while ((i < n) && (a[i] != '\0'))
    {
        h = ((h << 1) + h) + a[i] - 'a';
        i++;
    }
    if (i == n)
    {
        res += hashFind(h);
        while (a[i] != '\0')
        {
            h -= (a[i - n] - 'a') * POW3[n - 1];
            h = ((h << 1) + h) + (a[i] - 'a');
            res += hashFind(h);
            i++;
        }
    }
    out << res << '\n';
    return 0;
}