Pagini recente » Istoria paginii utilizator/adelindutu | Monitorul de evaluare | Rating Dragomir Ioan (ftsl) | Profil M@2Te4i | Cod sursa (job #2432764)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int BASE = 4;
const int MOD = 8191;
int getHashCode(string str) {
int h = 0;
for (int i = 0; i < (int) str.size(); i++)
h = (h * BASE + (str[i] - 'a' + 1)) % MOD;
return h;
}
int pow(int x, int n) {
if (!n)
return 1;
if (n & 1)
return x * pow(x * x % MOD, n >> 1) % MOD;
return pow(x * x % MOD, n >> 1);
}
int main() {
string str; fin >> str;
unordered_set<int> patterns; int len = 0;
string pattern;
while (fin >> pattern) {
len = pattern.size();
patterns.insert(getHashCode(pattern));
}
int h = getHashCode(str.substr(0, len));
int sol = (patterns.find(h) != patterns.end());
int pwr = pow(BASE, len - 1);
for (int i = len; i < (int) str.size(); i++) {
h = ((h - (str[i - len] - 'a' + 1) * pwr % MOD + MOD) * BASE + (str[i] - 'a' + 1)) % MOD;
sol += (patterns.find(h) != patterns.end());
}
fout << sol << '\n';
fout.close();
return 0;
}