Pagini recente » Cod sursa (job #1521317) | Cod sursa (job #2797838) | Cod sursa (job #2498621) | Cod sursa (job #505055) | Cod sursa (job #2295850)
#include <bits/stdc++.h>
using namespace std;
ifstream fi("abc2.in");
ofstream fo("abc2.out");
const int MOD1 = 666013, MOD2 = 1e9 + 7, B = 250;
using i64 = long long;
using pii = pair<int, int>;
unordered_set<i64> s;
string vsb, str;
int antwoord, len, n;
static pii get_hsh(const string &str) {
i64 h1 = 0, h2 = 0;
for (auto i: str) {
h1 = (h1 * B + i) % MOD1;
h2 = (h2 * B + i) % MOD2;
}
return pii(h1, h2);
}
static void fix(i64 &x, i64 &y) {
if (x < 0)
x+= MOD1;
if (y < 0)
y+= MOD2;
}
static i64 woord(const pii &hsh) {
return (1LL * hsh.first << 32) + hsh.second;
}
static i64 woord(const i64 &h1, const i64 &h2) {
return (1LL * h1 << 32) + h2;
}
int main(){
i64 h1 = 0, h2 = 0, pwr1 = 1, pwr2 = 1;
fi >> vsb;
n = vsb.size();
while (fi >> str) {
s.insert(woord(get_hsh(str)));
len = str.size();
}
for (int i = 0; i < len; ++i) {
h1 = (h1 * B + vsb[i]) % MOD1;
h2 = (h2 * B + vsb[i]) % MOD2;
if (i + 1 == len)
break;
pwr1 = pwr1 * B % MOD1;
pwr2 = pwr2 * B % MOD2;
}
antwoord+= int(s.find(woord(h1, h2)) != end(s));
for (int i = 0; i + len < n; ++i) {
h1 = (h1 - pwr1 * vsb[i]) % MOD1;
h2 = (h2 - pwr2 * vsb[i]) % MOD2;
fix(h1, h2);
h1 = (h1 * B + vsb[i + len]) % MOD1;
h2 = (h2 * B + vsb[i + len]) % MOD2;
if (s.find(woord(h1, h2)) != end(s))
antwoord+= 1;
}
fo << antwoord << endl;
cerr << antwoord << endl;
return 0;
}
/* Prostitutia
* nu este o recompensa adecvata codatului byat proola
*/