Cod sursa(job #2470320)

Utilizator mirceatlxhaha haha mirceatlx Data 8 octombrie 2019 23:47:10
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <string>
#pragma GCC optimize("O3")
#include <cstring>
#define MOD 5099
using namespace std;

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

char word[25];
char str[10000005];
int lgw;
vector < unsigned int > H[MOD];

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

int Find(unsigned int x)
{
    int key = x % MOD;
    for(auto it : H[key])
        if(it == x)
            return 1;
    return 0;
}

void Insert(int x)
{
    int key = x % MOD;
    int it = Find(x);
    if (it == 0)
        H[key].push_back(x);
}

int main()
{
    unsigned int power = 1, result = 0;
    fin >> str;
    while(fin >> word)
        Insert(keyFinding());
    unsigned int HashValue = 0, lg = strlen(str);
    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)
            result += Find(HashValue);
    }
    fout << result << "\n";
    return 0;

}