Pagini recente » Cod sursa (job #1832778) | Cod sursa (job #2104075) | Cod sursa (job #950889) | Cod sursa (job #735466) | Cod sursa (job #2783797)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("abc2.in");
ofstream fout("abc2.out");
const int MAXN = 1e7;
const int MAXL = 20;
const int mod = 49157;
char s[1 + MAXN], t[1 + MAXL];
vector<unsigned> hash_table[mod];
void Insert(unsigned x) {
int key = x % mod;
for (auto it : hash_table[key]) {
if (it == x) {
return;
}
}
hash_table[key].emplace_back(x);
}
bool check(unsigned x) {
int key = x % mod;
for (auto it : hash_table[key]) {
if (it == x) {
return true;
}
}
return false;
}
void test_case() {
fin >> s;
int m = 0;
while (fin >> t) {
m = strlen(t);
unsigned val = 0;
for (int i = 0; i < m; ++i) {
val = val * 3 + (t[i] - 'a');
}
Insert(val);
}
unsigned val = 0, pw = 1;
for (int i = 0; i < m; ++i) {
val = val * 3 + (s[i] - 'a');
pw *= 3;
}
pw /= 3;
int n = strlen(s), 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;
}