Pagini recente » Cod sursa (job #2909198) | Cod sursa (job #328160) | Cod sursa (job #2375349) | Cod sursa (job #2411779) | Cod sursa (job #3266654)
#include <bits/stdc++.h>
using namespace std;
const int p = 3, MOD = 66013;
string text, word;
vector<unsigned int> m[MOD];
bool searchHash(unsigned int k) {
int r = k % MOD;
for (int i = 0; i < m[r].size(); ++i) {
if (m[r][i] == k) {
return 1;
}
}
return 0;
}
void insertHash(unsigned int k) {
int r = k % MOD;
if (!searchHash(k)) {
m[r].push_back(k);
}
}
unsigned int hashF(string word) {
unsigned int res = 0;
for (int i = 0; i < word.size(); ++i) {
res = res * p + (word[i] - 'a');
}
return res;
}
unsigned int calcPow(int base, int power) {
unsigned int res = 1;
for (int i = 1; i <= power; ++i) {
res *= base;
}
return res;
}
int main() {
ifstream cin("abc2.in");
ofstream cout("abc2.out");
cin >> text;
while (cin >> word) {
insertHash(hashF(word));
}
int wSize = word.size();
unsigned int res = 0, pos = 0, ans = 0;
unsigned int last = calcPow(3, wSize - 1);
for (int i = 0; i < text.size(); ++i) {
res = res * p + (text[i] - 'a');
if (i >= wSize - 1) {
if (searchHash(res)) {
++ans;
}
res = res - last * (text[i - (wSize - 1)] - 'a');
}
}
cout << ans;
}