Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 145 si 223 | Cod sursa (job #1993368) | Cod sursa (job #570710) | Cod sursa (job #715024) | Cod sursa (job #2108170)
#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
class HashTable {
private:
std::vector<std::vector<size_t>> table;
size_t mod = 666013;
inline size_t hashFunc(const size_t &key) {
return key % this->mod;
}
bool find(const size_t &key, const bool &add, const bool &erase) {
const size_t hashedKey = this->hashFunc(key);
for (size_t &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 size_t mod=666013) {
this->mod = mod;
this->table.assign(this->mod, std::vector<size_t>());
}
bool has(const size_t &key) {
return this->find(key, false, false);
}
bool add(const size_t &key) {
return this->find(key, true, false);
}
bool erase(const size_t &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) {
size_t hashCode = 0;
for (const char &ch: word) {
hashCode = hashCode * 3 + ch - 'a';
}
hashTable.add(hashCode);
}
if (str.length() < word.length()) {
cout << 0 << std::endl;
return 0;
}
// 3 ^ (word.length() - 1)
size_t power = 1;
for (int i = 1; i < word.length(); ++ i) {
power *= 3;
}
size_t rollingHash = 0;
for (int i = 0; i < word.length(); ++ i) {
rollingHash = rollingHash * 3 + str[i] - 'a';
}
size_t result = 0;
if (hashTable.has(rollingHash)) {
result += 1;
}
for (int i = word.length(); i < str.length(); ++ i) {
rollingHash -= power * (str[i - word.length()] - 'a');
rollingHash = rollingHash * 3 + str[i] - 'a';
if (hashTable.has(rollingHash)) {
result += 1;
}
}
cout << result << std::endl;
return 0;
}