Cod sursa(job #1880106)

Utilizator enacheionutEnache Ionut enacheionut Data 15 februarie 2017 15:05:47
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>

#define MOD_NUMBER 666013

using namespace std;

string text;
unsigned int wordLength = 0;
vector<vector<unsigned int>> dictionary(MOD_NUMBER, vector<unsigned int>());

void ReserveSpaceForDictionary()
{
    for( unsigned int index = 0; index < dictionary.size(); ++index )
    {
        dictionary[index].reserve(MOD_NUMBER);
    }
}

unsigned int CreatHashCode(unsigned int encodedWord)
{
    return encodedWord % MOD_NUMBER;
}

unsigned int EncodeWord(string word)
{
    unsigned int encodedWord = 0;
    for( unsigned int index = 0; index < wordLength; ++index )
    {
        encodedWord = encodedWord * 3 + word[index] - 'a';
    }
    return encodedWord;
}

void AddWord(unsigned int encodedWord)
{
    unsigned int hashCode = CreatHashCode(encodedWord);
    for( unsigned int index = 0; index < dictionary[hashCode].size(); ++index )
        if( dictionary[hashCode][index] == encodedWord )
           return;
    dictionary[hashCode].push_back(encodedWord);
}

void ReadInput()
{
    unsigned int encodedWord = 0;
    string word;
    ifstream inputStream("abc2.in");

    inputStream>> text>> word;

    wordLength = word.length();
    encodedWord = EncodeWord(word);
    AddWord(encodedWord);

    while( !inputStream.eof() )
    {
        inputStream>> word;
        encodedWord = EncodeWord(word);
        AddWord(encodedWord);
    }
}

bool FindWord(unsigned int encodedWord)
{
    unsigned int hashCode = CreatHashCode(encodedWord);
    for( unsigned int index = 0; index < dictionary[hashCode].size(); ++index )
        if( dictionary[hashCode][index] == encodedWord )
            return true;
    return false;
}

unsigned int CalculateNumberOfPositions()
{
    unsigned int numberOfPositions = 0;
    unsigned int textLength = text.length();

    unsigned int encodedWord = EncodeWord(text.substr(0, wordLength));
    numberOfPositions += FindWord(encodedWord);

    unsigned int aux = pow(3, wordLength) / 3;
    for( unsigned int index = wordLength; index < textLength; ++index )
    {
        encodedWord -= aux * (text[index - wordLength] - 'a');
        encodedWord = encodedWord * 3 + text[index] - 'a';
        numberOfPositions += FindWord(encodedWord);
    }
    return numberOfPositions;
}

void DisplayResult(unsigned int numberOfPositions)
{
    ofstream outputStream("abc2.out");
    outputStream<< numberOfPositions;
    outputStream.close();
}

int main()
{
    ReadInput();
    unsigned int numberOfPositions = CalculateNumberOfPositions();
    DisplayResult(numberOfPositions);
}