Cod sursa(job #1783775)

Utilizator PletoPletosu Cosmin-Andrei Pleto Data 19 octombrie 2016 14:16:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda hash_excelenta Marime 1.06 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

unsigned int solutie, cod, puteri3[20];
const int mod = (1<<19)-1;
char V[10000000], cuv[20];
vector <int> H[mod];

int isInHash(int x)
{
    vector <int> :: iterator it=H[x%mod].begin(), sf=H[x%mod].end();
    for(; it!=sf; ++it) if(*it == x) return 1;
    return 0;
}

int main()
{
    fin>>V;
    int N = strlen(V), M;
    puteri3[0]=1;
    for(int i=1; i<20; ++i)
    {
        puteri3[i] = puteri3[i-1]*3;
    }
    while(fin>>cuv)
    {
        M=strlen(cuv);
        cod = 0;
        for(int i=0; i<M; ++i)
        {
            cod = cod + puteri3[i]*(cuv[i]-'a');
            H[cod%mod].push_back(cod);
        }
    }
    for(int i=0; i<M; ++i)
        cod = cod + puteri3[i]*(V[i]-'a');
    solutie += isInHash(cod);
    for(int i=M; i<N; ++i)
    {
        cod /= 3;
        cod = cod + puteri3[M-1]*(V[i]-'a');
        solutie += isInHash(cod);;
    }
    fout<<solutie<<'\n';
    return 0;
}