Cod sursa(job #2106872)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 16 ianuarie 2018 13:11:01
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 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;
const int Modulo = 233197;
vector <unsigned int> Lists[Modulo];

void insertHash(unsigned int Value)
{
    int key = Value % Modulo;
    Lists[key].push_back(Value);
}

bool findHash(unsigned int Value)
{
    int key = Value % Modulo;
    for(auto it : Lists[key])
        if(it == Value)
            return 1;
    return 0;
}

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

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

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

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

    int answer = 0;
    if(findHash(hashCode))
        answer++;

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

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