Pagini recente » Cod sursa (job #2459605) | Cod sursa (job #575815) | Cod sursa (job #2817758) | Cod sursa (job #455348) | Cod sursa (job #2101576)
#include <fstream>
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
const int Mod = 90907;
const int Base = 3;
string text, word;
int H[Mod];
long long firstExp = 1;
int Hash(string str) {
long long currHash = 0;
for (int i = 0; i < str.size(); ++i) {
currHash *= Base;
currHash += str[i] - 'a';
currHash %= Mod;
}
return currHash;
}
void UpdateRollingHash(int stPos, int edPos, long long &currHash) {
currHash -= (text[stPos] - 'a') * firstExp;
currHash += Mod;
currHash %= Mod;
currHash *= Base;
// currHash %= Mod[type];
currHash += text[edPos + 1] - 'a';
currHash %= Mod;
}
int main() {
cin >> text;
int wordSize = 0;
while (cin >> word) {
wordSize = word.size();
H[Hash(word)] = true;
// cout << Hash(word) << ' ';
}
// cout << '\n';
for (int i = 1; i < wordSize; ++i) {
firstExp *= Base;
}
firstExp %= Mod;
if (text.size() < wordSize) {
cout << 0 << '\n';
return 0;
}
string startStr;
for (int i = 0; i < wordSize; ++i) {
startStr.push_back(text[i]);
}
int ans = 0;
long long hash = Hash(startStr);
// cout << hash << ' ';
if (H[hash]) {
++ans;
}
for (int i = 1; i + wordSize - 1 < text.size(); ++i) {
UpdateRollingHash(i - 1, i + wordSize - 2, hash);
// cout << hash << ' ';
if (H[hash]) {
++ans;
}
}
// cout << '\n';
cout << ans << '\n';
return 0;
}