Pagini recente » Cod sursa (job #2270020) | Cod sursa (job #165959) | Istoria paginii utilizator/butnaru_vlad | Probleme de Taietura | Cod sursa (job #2297388)
#include <bits/stdc++.h>
#pragma GCC optimize("03")
#define MOD1 1231
#define MOD2 1323
using namespace std;
ifstream in("abc2.in");
ofstream out("abc2.out");
char s[10000100], g[50100];
int sz, gz, pw1[30], pw2[30], ans;
vector <int> v[MOD1 + 123];
bool get(int key, int elem) {
for (auto i : v[key])
if (i == elem)
return 1;
return 0;
}
void baga(int key, int elem) {
if (!get(key, elem))
v[key].push_back(elem);
}
int main() {
pw1[0] = pw2[0] = 1;
for (int i = 1; i <= 21; i++) {
pw1[i] = (pw1[i - 1] * 5) % MOD1;
pw2[i] = (pw2[i - 1] * 5) % MOD2;
}
in >> s;
while (in >> g) {
gz = strlen(g);
int hsh1 = 0, hsh2 = 0;
for (int i = 0; i < gz; i++) {
hsh1 = (hsh1 + (int) g[i] * pw1[gz - i - 1]) % MOD1;
hsh2 = (hsh2 + (int) g[i] * pw2[gz - i - 1]) % MOD2;
}
baga(hsh1, hsh2);
}
sz = strlen(s);
int hsh1 = 0, hsh2 = 0;
for (int i = 0; i < gz; i++) {
hsh1 = (hsh1 + (int) s[i] * pw1[gz - i - 1]) % MOD1;
hsh2 = (hsh2 + (int) s[i] * pw2[gz - i - 1]) % MOD2;
}
ans += get(hsh1, hsh2);
for (int i = gz; i < sz; i++) {
hsh1 = ((5 * hsh1 - pw1[gz] * (int) s[i - gz] + s[i]) % MOD1 + MOD1) % MOD1;
hsh2 = ((5 * hsh2 - pw2[gz] * (int) s[i - gz] + s[i]) % MOD2 + MOD2) % MOD2;
ans += get(hsh1, hsh2);
}
out << ans;
return 0;
}