Pagini recente » Cod sursa (job #410929) | Cod sursa (job #2071010) | Cod sursa (job #1967593) | Cod sursa (job #2736872) | Cod sursa (job #2297351)
#include <bits/stdc++.h>
#define MOD1 104053
#define MOD2 104059
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
string s, g;
int sz, gz, pw[30], ans;
vector <int> v[MOD2 + 123];
bool get(int key) {
for (auto i : v[key % MOD2])
if (i == key)
return 1;
return 0;
}
void baga(int key) {
if (!get(key))
v[key % MOD2].push_back(key);
}
int main() {
pw[0] = 1;
for (int i = 1; i <= 21; i++)
pw[i] = (pw[i - 1] * 31) % MOD1;
in >> s;
while (in >> g) {
gz = g.size();
int hsh = 0;
for (int i = 0; i < gz; i++)
hsh = (hsh + (int) g[i] * pw[gz - i - 1]) % MOD1;
baga(hsh);
}
sz = s.size();
int hsh = 0;
for (int i = 0; i < gz; i++)
hsh = (hsh + (int) s[i] * pw[gz - i - 1]) % MOD1;
ans += get(hsh);
for (int i = gz; i < sz; i++) {
hsh = ((31 * hsh - pw[gz] * (int) s[i - gz] + s[i]) % MOD1 + MOD1) % MOD1;
ans += get(hsh);
}
out << ans;
return 0;
}