Cod sursa(job #1751218)

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

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

int exists (int hash_value)
{
    int key = hash_value % MOD;
    for(vector<int>:: iterator it = hashmap[key].begin(); it != hashmap[key].end(); it++)
        if (*it == hash_value)
            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;
}