Pagini recente » Cod sursa (job #3311512) | Cod sursa (job #2238516) | Cod sursa (job #3342689) | Cod sursa (job #3304035) | Cod sursa (job #3318150)
#include <bits/stdc++.h>
using namespace std;
const int HASH_BASE = 3;
string text;
string word;
unordered_set<unsigned int> wordHashes;
unsigned int computeHash(const string &word) {
unsigned int hashValue = 0;
for (char c : word) {
hashValue = hashValue * HASH_BASE + (c - 'a');
}
return hashValue;
}
unsigned int powUnsigned(int base, int power) {
unsigned int result = 1;
for (int i = 1; i <= power; ++i) {
result *= base;
}
return result;
}
int main() {
ifstream inputFile("abc2.in");
ofstream outputFile("abc2.out");
inputFile >> text;
while (inputFile >> word) {
wordHashes.insert(computeHash(word));
}
int wordLength = word.size();
unsigned int currentHash = 0;
unsigned int highestPow = powUnsigned(HASH_BASE, wordLength - 1);
int matchCount = 0;
for (int i = 0; i < text.size(); ++i) {
currentHash = currentHash * HASH_BASE + (text[i] - 'a');
if (i >= wordLength - 1) {
if (wordHashes.find(currentHash) != wordHashes.end()) {
++matchCount;
}
currentHash -= highestPow * (text[i - (wordLength - 1)] - 'a');
}
}
outputFile << matchCount;
}