Pagini recente » Cod sursa (job #767931) | Cod sursa (job #140844) | Cod sursa (job #2220664) | Rating Calin Stafie (Starkiller) | Cod sursa (job #2101543)
#include <fstream>
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
const int Mod[] = {105499, 106961};
const int MaxMod = 107000;
const int Base = 73;
string text, word;
int H[2][MaxMod];
long long firstExp[2] = {1, 1};
int Hash(string str, int type) {
long long currHash = 0;
for (int i = 0; i < str.size(); ++i) {
currHash *= Base;
currHash += str[i] - 'a';
currHash %= Mod[type];
}
return currHash;
}
void UpdateRollingHash(int stPos, int edPos, long long &currHash, int type) {
currHash -= (text[stPos] - 'a') * firstExp[type];
currHash += Mod[type];
currHash %= Mod[type];
currHash *= Base;
currHash %= Mod[type];
currHash += text[edPos + 1] - 'a';
currHash %= Mod[type];
}
int main() {
cin >> text;
int wordSize = 0;
while (cin >> word) {
wordSize = word.size();
H[0][Hash(word, 0)] = true;
H[1][Hash(word, 1)] = true;
// cout << Hash(word, 0) << ' ' << Hash(word, 1) << '\n';
}
for (int i = 1; i < wordSize; ++i) {
for(int type = 0; type <= 1; ++type) {
firstExp[type] *= Base;
firstExp[type] %= Mod[type];
}
}
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, 0), Hash(startStr, 1)};
// cout << hash[0] << ' ' << hash[1] << '\n';
if (H[0][hash[0]] and H[1][hash[1]]) {
++ans;
}
// cout << Hash("bcab", 0) << ' ' << Hash("bcab", 1) << '\n' << "---------------------------\n";
for (int i = 1; i + wordSize - 1 < text.size(); ++i) {
UpdateRollingHash(i - 1, i + wordSize - 2, hash[0], 0);
UpdateRollingHash(i - 1, i + wordSize - 2, hash[1], 1);
// if (i == 1) {
// cout << hash[0] << ' ' << hash[1] << '\n';
// }
if (H[0][hash[0]] and H[1][hash[1]]) {
++ans;
}
}
cout << ans << '\n';
return 0;
}