Pagini recente » Cod sursa (job #2589040) | Cod sursa (job #1507566) | Cod sursa (job #2650089) | Cod sursa (job #1652078) | Cod sursa (job #1879596)
#include <iostream>
#include <fstream>
#include <set>
#include <unordered_map>
#include <math.h>
#define MOD_NUMBER 666013
using namespace std;
string text;
unsigned int wordLength = 0;
unordered_map<unsigned int, set<unsigned int>> dictionary;
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 = encodedWord % MOD_NUMBER;
dictionary[hashCode].insert(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 = encodedWord % MOD_NUMBER;
return *dictionary[hashCode].lower_bound(encodedWord) == encodedWord;
}
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);
}