Cod sursa(job #1751221)

Utilizator petrooPetru G petroo Data 31 august 2016 22:44:36
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <string.h>
#include <stdio.h>
#include <vector>
#include <algorithm>
#define Nmax 10000005
#define Mmax 50005
#define MOD 666013
using namespace std;

vector <int> hashmap[MOD + 5];
long long h[22];
char text[Nmax],cuv[Mmax];

int exists (int hash_value)
{
    int key = hash_value % MOD;
    if(find(hashmap[key].begin(), hashmap[key].end(), hash_value) != hashmap[key].end())
        return 1;
    return 0;
}

int main()
{
    int sol = 0;
    int hash_value = 0, n, m;
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    h[0] = 1;
    for(int i = 1; i <= 21; i++)
        h[i] = 3 * h[i-1];
    fgets(text, Nmax, stdin);
    while (fgets(cuv, Mmax,stdin) != NULL)
    {
        hash_value = 0;
        n = strlen(cuv) - 1;
        cuv[n] = 0;
        for( int i = 0; i < n; i++)
            hash_value += ( cuv[i] - 'a' ) * h[i];
        if ( !exists(hash_value))
            hashmap[hash_value % MOD].push_back(hash_value);
    }
    hash_value = 0;
    for (int i = 0; i < n; i++)
        hash_value += (text[i] - 'a' ) * h[i];

    if(exists(hash_value))
        ++sol;
    m = strlen(text) - 1;
    for(int i = n; i < m; i++)
    {
        hash_value /= 3;
        hash_value += (text[i] - 'a' ) * h[n - 1];
        if (exists(hash_value))
            ++sol;
    }

    printf("%d", sol);

    return 0;
}