Pagini recente » Cod sursa (job #1743387) | Cod sursa (job #2861540) | Cod sursa (job #2452589) | Cod sursa (job #941168) | Cod sursa (job #1828883)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
template<typename T>
class Hash {
public:
Hash() :
m_hashTable(kMod) {
}
void Add(T key) {
for (T it : m_hashTable[key % kMod])
if (it == key)
return;
m_hashTable[key % kMod].push_back(key);
}
bool Find(T key) {
for (T it : m_hashTable[key % kMod])
if (it == key)
return true;
return false;
}
private:
std::vector< std::vector<T> > m_hashTable;
static constexpr int kMod = 666013;
};
class Solver {
public:
Solver() {
}
void LoadTest(const std::string path) {
std::ifstream inputFile(path);
inputFile >> m_text;
std::string word;
while (inputFile >> word) {
m_wordLen = (int)word.length();
unsigned int val = 0;
for (auto letter : word)
val = val*kBase + (letter - 'a');
m_hashManager.Add(val);
}
inputFile.close();
}
void PrintSolution(const std::string path) {
std::ofstream outputFile(path);
outputFile << CountMatches() << '\n';
outputFile.close();
}
private:
int CountMatches() {
unsigned int val = 0, power = 1;
for (int i = 0; i < m_wordLen; ++i) {
val = val*3 + (m_text[i] - 'a');
power *= 3;
}
power /= 3;
int res = 0;
if (m_hashManager.Find(val))
res++;
for (int i = m_wordLen; i < (int)m_text.size(); ++i) {
val -= (m_text[i - m_wordLen] - 'a')*power;
val = 3*val + (m_text[i] - 'a');
if (m_hashManager.Find(val))
res++;
}
return res;
}
int m_wordLen;
std::string m_text;
Hash<unsigned int> m_hashManager;
static constexpr int kBase = 3;
};
int main() {
Solver solver;
solver.LoadTest("abc2.in");
solver.PrintSolution("abc2.out");
return 0;
}
//Trust me, I'm the Doctor!