Pagini recente » Cod sursa (job #826428) | Cod sursa (job #2046521) | Cod sursa (job #2876164) | Cod sursa (job #50102) | Cod sursa (job #2101622)
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("abc2.in");
ofstream cout("abc2.out");
const int Mod = 90907;
const int Base = 3;
string text, word;
vector <unsigned int> H[Mod];
unsigned int firstExp = 1;
inline unsigned int Hash(string str) {
unsigned int currHash = 0;
for (int i = 0; i < str.size(); ++i) {
currHash *= Base;
currHash += str[i] - 'a';
// currHash %= Mod;
}
return currHash;
}
inline bool FindHash(unsigned int hash) {
unsigned int modHash = hash % Mod;
for (int i = 0; i < H[modHash].size(); ++i) {
if (H[modHash][i] == hash) {
return true;
}
}
return false;
}
inline void UpdateRollingHash(int stPos, int edPos, unsigned int &currHash) {
currHash -= (text[stPos] - 'a') * firstExp;
currHash *= Base;
currHash += text[edPos + 1] - 'a';
}
int main() {
getline(cin, text);
int wordSize = 0;
while (getline(cin, word)) {
wordSize = word.size();
unsigned int hash = Hash(word);
if (!FindHash(hash)) {
H[hash % Mod].push_back(hash);
}
}
if (text.size() < wordSize) {
cout << 0 << '\n';
return 0;
}
string startStr;
for (int i = 0; i < wordSize; ++i) {
firstExp *= Base;
startStr.push_back(text[i]);
}
firstExp /= Base;
int ans = 0;
unsigned int hash = Hash(startStr);
ans += FindHash(hash);
for (int i = 1; i + wordSize - 1 < text.size(); ++i) {
UpdateRollingHash(i - 1, i + wordSize - 2, hash);
ans += FindHash(hash);
}
cout << ans << '\n';
return 0;
}