Pagini recente » Cod sursa (job #1903400) | Cod sursa (job #967975) | Cod sursa (job #674627) | Cod sursa (job #2597144) | Cod sursa (job #2297360)
#include <bits/stdc++.h>
#define MOD1 104053
#define MOD2 104059
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char s[10000100], g[50100];
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 = strlen(g);
int hsh = 0;
for (int i = 0; i < gz; i++)
hsh = (hsh + (int) g[i] * pw[gz - i - 1]) % MOD1;
baga(hsh);
}
sz = strlen(s);
int hsh = 0;
for (int i = 0; i < gz; i++)
hsh = (hsh + (int) s[i] * pw[gz - i - 1]) % MOD1;
baga(hsh);
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;
}