Pagini recente » Cod sursa (job #2207532) | Cod sursa (job #2816492) | Cod sursa (job #1811042) | Cod sursa (job #278731) | Cod sursa (job #2108174)
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
typedef std::uint32_t uint32;
class HashTable {
private:
std::vector<std::vector<uint32>> table;
uint32 mod = 666013;
inline uint32 hashFunc(const uint32 &key) {
return key % this->mod;
}
bool find(const uint32 &key, const bool &add, const bool &erase) {
const uint32 hashedKey = this->hashFunc(key);
for (uint32 &value: this->table[hashedKey]) {
if (value == key) {
if (erase) {
value = this->table[hashedKey].back();
this->table[hashedKey].pop_back();
return false;
}
return true;
}
}
if (add) {
this->table[hashedKey].push_back(key);
return true;
}
return false;
}
public:
HashTable(const uint32 mod=666013) {
this->mod = mod;
this->table.assign(this->mod, std::vector<uint32>());
}
bool has(const uint32 &key) {
return this->find(key, false, false);
}
bool add(const uint32 &key) {
return this->find(key, true, false);
}
bool erase(const uint32 &key) {
return this->find(key, false, true);
}
};
int main() {
std::ifstream cin("abc2.in");
std::ofstream cout("abc2.out");
std::string str;
std::string word;
HashTable hashTable;
cin >> str;
while (cin >> word) {
uint32 hashCode = 0;
for (const char &ch: word) {
hashCode = hashCode * 3 + ch - 'a';
}
hashTable.add(hashCode);
}
uint32 strLength = str.length();
uint32 wordLength = word.length();
if (strLength < wordLength) {
cout << 0 << std::endl;
return 0;
}
// 3 ^ (wordLength - 1)
uint32 power = 1;
for (int i = 1; i < wordLength; ++ i) {
power *= 3;
}
uint32 rollingHash = 0;
for (int i = 0; i < wordLength; ++ i) {
rollingHash = rollingHash * 3 + str[i] - 'a';
}
uint32 result = 0;
if (hashTable.has(rollingHash)) {
result += 1;
}
for (int i = wordLength; i < strLength; ++ i) {
rollingHash -= power * (str[i - wordLength] - 'a');
rollingHash = rollingHash * 3 + str[i] - 'a';
if (hashTable.has(rollingHash)) {
result += 1;
}
}
cout << result << std::endl;
return 0;
}