Cod sursa(job #2470299)

Utilizator mirceatlxhaha haha mirceatlx Data 8 octombrie 2019 23:11:31
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.62 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <string>
#define MOD 6660
using namespace std;

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

string str, word;
int lgw;
vector < unsigned int > H[MOD];

int keyFinding(string Word)
{
    int key = 0, lg = Word.size(); // might optimise in here
    lgw = lg;
    for(int i = 0; i < lg; i++)
        key = key  * 3 + (Word[i] - 'a');
    return key;
}

vector < unsigned int > :: iterator Find(int x)
{
    int key = x % MOD;
    vector < unsigned int > :: iterator it;
    for(it = H[key].begin(); it != H[key].end(); ++it)
        if(*it == x)
            return it;
    return H[key].end();
}

bool FindFinal(int x)
{
    int key = x % MOD;
    vector < unsigned int > :: iterator it;
    for(it = H[key].begin(); it != H[key].end(); ++it)
        if(*it == x)
            return true;
    return false;
}

void Insert(int x)
{
    int key = x % MOD;
    vector < unsigned int > :: iterator it = Find(x);
    if (it != H[key].end())
        return;
    H[key].push_back(x);
}

int main()
{
    int power = 1, result = 0;
    fin >> str;
    while(fin >> word)
        Insert(keyFinding(word));
    int HashValue = 0, lg = str.size();
    for(int i = 1; i <= lgw; i++)
        power *= 3;
    for(int i = 0; i < lg; i++)
    {
        HashValue = HashValue * 3 + (str[i] - 'a');

        if(i >= lgw)
            HashValue = HashValue - power * (str[i - lgw] - 'a');

        if(i >= lgw - 1)
            if(FindFinal(HashValue))
                result++;
    }
    fout << result << "\n";
    return 0;

}