Pagini recente » Cod sursa (job #2788751) | Cod sursa (job #153560) | Cod sursa (job #2754984) | Cod sursa (job #276763) | Cod sursa (job #1880129)
#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <math.h>
#define MOD_NUMBER 666013
using namespace std;
string text;
unsigned int wordLength = 0;
vector<unsigned int> dictionary[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);
}