Pagini recente » Cod sursa (job #1249080) | Cod sursa (job #2701856) | Cod sursa (job #2709321) | Cod sursa (job #3152684) | Cod sursa (job #2297392)
// NU VA APUCATI DE CACATU ASTA DE PROBLEMA
#include <bits/stdc++.h>
#pragma GCC optimize("03")
#define MOD 29317
#define ll long long
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char s[10000100], g[50100];
int sz, gz, ans;
ll pw[30];
vector <ll> v[MOD];
bool get(ll key) {
for (auto i : v[key % MOD])
if (i == key)
return 1;
return 0;
}
int main() {
pw[0] = 1;
for (int i = 1; i <= 21; i++)
pw[i] = 3LL * pw[i - 1];
in >> s;
while (in >> g) {
gz = strlen(g);
ll hsh = 0;
for (int i = 0; i < gz; i++)
hsh = 3LL * hsh + g[i] - 48;
if (!get(hsh))
v[hsh % MOD].push_back(hsh);
}
sz = strlen(s);
ll hsh = 0;;
for (int i = 0; i < gz; i++) {
hsh = 3LL * hsh + s[i] - 48;
}
ans += get(hsh);
for (int i = gz; i < sz; i++) {
hsh = 3LL * hsh - pw[gz] * (s[i - gz] - 48) + s[i] - 48;
ans += get(hsh);
}
out << ans;
return 0;
}