Pagini recente » Cod sursa (job #1425412) | Cod sursa (job #1050692) | Cod sursa (job #3142617) | Cod sursa (job #462590) | Cod sursa (job #2474158)
#include <bits/stdc++.h>
#define llg unsigned int
#pragma GCC optimize("O3")
#define MOD 133337
template <llg P> class HashTable {
public:
HashTable() {}
void insert(llg value) {
if (value < 0) value = value%MOD + MOD;
llg list = value%P;
value /= P;
for (auto &it:hash[list])
if (it == value) return;
hash[list].push_back(value);
}
bool contains(llg value) {
if (value < 0) value = value%MOD + MOD;
llg list = value%P;
value /= P;
for (auto &it:hash[list])
if (it == value) return true;
return false;
}
private:
std::list <llg> hash[P + 1000];
}; HashTable <MOD> Hash;
llg len;
std::string str;
std::ifstream input ("abc2.in");
std::ofstream output("abc2.out");
int main()
{
input >> str;
std::string word;
while (input >> word) {
len = word.size();
llg hash = 0;
for (llg i=0; i<word.size(); ++i)
hash = hash*3 + word[i]-'a';
Hash.insert(hash);
}
llg p = 1, ans = 0;
for (llg i=0; i<len; ++i)
p *= 3;
llg hash = 0;
for (int i=0; i<len; ++i)
hash = hash*3 + str[i]-'a';
ans += Hash.contains(hash);
for (llg i=len; i<str.size(); ++i) {
hash = hash*3 + str[i]-'a';
hash = hash - p*(str[i-len]-'a');
ans += Hash.contains(hash);
} output << ans << '\n';
return 0;
}