Cod sursa(job #2106865)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 16 ianuarie 2018 13:01:56
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

const int LenMax = 10000005;
const int WordLenMax = 30;
char Text[LenMax], Word[WordLenMax];
int TextSize, WordSize;

const int Base = 3;
unordered_map <long long, bool> HashTable;

int main()
{
    ifstream cin("abc2.in");
    ofstream cout("abc2.out");
    cin >> Text;
    TextSize = strlen(Text);
    while(cin >> Word)
    {
        WordSize = strlen(Word);
        long long hashCode = 0;
        for(int i = 0; i < WordSize; i++)
            hashCode = hashCode * Base + Word[i] - 'a';
        HashTable[hashCode] = 1;
    }

    if(TextSize < WordSize)
    {
        cout << "0\n";
        return 0;
    }

    long long Power = 1;
    for(int i = 1; i < WordSize; i++)
        Power *= Base;

    long long hashCode = 0;
    for(int i = 0; i < WordSize; i++)
        hashCode = hashCode * Base + Text[i] - 'a';

    int answer = 0;
    if(HashTable.find(hashCode) != HashTable.end())
        answer++;

    for(int i = WordSize; i < TextSize; i++)
    {
        hashCode -= (Text[i - WordSize] - 'a') * Power;
        hashCode = hashCode * Base + Text[i] - 'a';
        if(HashTable.find(hashCode) != HashTable.end())
            answer++;
    }

    cout << answer << "\n";
    return 0;
}