Pagini recente » Cod sursa (job #1309644) | Cod sursa (job #2433793) | Cod sursa (job #1117442) | Cod sursa (job #1076080) | Cod sursa (job #2783793)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int mod = 1572869;
vector<int> hash_table[mod];
void Insert(int64_t x) {
int key = x % mod;
for (int it : hash_table[key]) {
if (it == x) {
return;
}
}
hash_table[key].emplace_back(x);
}
bool check(int64_t x) {
int key = x % mod;
for (int it : hash_table[key]) {
if (it == x) {
return true;
}
}
return false;
}
void test_case() {
string s, t;
fin >> s;
int m;
while (fin >> t) {
m = t.size();
int64_t val = 0;
for (char c : t) {
val = val * 3 + (c - 'a');
}
Insert(val);
}
int64_t val = 0, pw = 1;
for (int i = 0; i < m; ++i) {
val = val * 3 + (s[i] - 'a');
pw *= 3;
}
pw /= 3;
int n = s.size();
int ans = check(val);
for (int i = m; i < n; ++i) {
val -= pw * (s[i - m] - 'a');
val = val * 3 + (s[i] - 'a');
ans += check(val);
}
fout << ans << '\n';
}
int main() {
int t = 1;
for (int tc = 1; tc <= t; ++tc) {
test_case();
}
fin.close();
fout.close();
return 0;
}