Pagini recente » Cod sursa (job #130041) | Cod sursa (job #1862831) | Cod sursa (job #1202824) | Cod sursa (job #1971472) | Cod sursa (job #2432787)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int BASE = 3;
unsigned int getHashCode(string str) {
unsigned int h = 0;
for (int i = 0; i < (int) str.size(); i++)
h = h * BASE + (str[i] - 'a');
return h;
}
class HashTable {
private:
static const int MOD = 7001;
vector<unsigned int> table[MOD];
public:
void insert(unsigned int val) {
int hash = val % MOD;
for (unsigned int i : table[hash])
if (i == val)
return;
table[hash].push_back(val);
}
bool find(unsigned int val) {
int hash = val % MOD;
for (unsigned int i : hash[table])
if (i == val)
return true;
return false;
}
};
int main() {
string str; fin >> str;
HashTable patterns; int len = 0;
string pattern;
while (fin >> pattern) {
len = pattern.size();
patterns.insert(getHashCode(pattern));
}
unsigned int h = getHashCode(str.substr(0, len));
int sol = patterns.find(h);
unsigned int pwr = 1;
for (int i = 1; i < len; i++)
pwr *= BASE;
for (int i = len; i < (int) str.size(); i++) {
h = (h - (str[i - len] - 'a') * pwr) * BASE + (str[i] - 'a');
sol += patterns.find(h);
}
fout << sol << '\n';
fout.close();
return 0;
}