Pagini recente » Cod sursa (job #2443441) | Cod sursa (job #2189355) | Cod sursa (job #2374206) | Cod sursa (job #2604969) | Cod sursa (job #2474145)
#include <bits/stdc++.h>
#define llg unsigned int
#define MOD 5099
template <int P> class HashTable {
public:
HashTable() {
}
void insert(int value) {
int list = value%P;
value /= P;
for (auto &it:hash[list])
if (it == value) return;
hash[list].push_back(value);
}
bool contains(int value) {
int list = value%P;
value /= P;
for (auto &it:hash[list])
if (it == value) return true;
return false;
}
private:
std::list <int> hash[P];
}; HashTable <MOD> Hash;
int 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 (int i=0; i<(int) word.size(); ++i)
hash = hash*3 + word[i]-'a';
Hash.insert(hash);
}
llg p = 1, ans = 0;
for (int i=0; i<len; ++i)
p *= 3;
for (llg i=0, hash=0; i<(llg) str.size(); ++i) {
hash = hash*3 + str[i]-'a';
if (i>=len) hash = hash - p*(str[i-len]-'a');
if (i>=len-1) ans += (int) Hash.contains(hash);
} output << ans << '\n';
return 0;
}