Pagini recente » Istoria paginii runda/concurs_11_12_02_23/clasament | Cod sursa (job #774395) | Cod sursa (job #1542306) | Istoria paginii runda/pt_round12/clasament | Cod sursa (job #2783799)
#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 = 12289;
const int MASK = (1 << 23) - 1;
char s[1 + MAXN], t[1 + MAXL];
bitset<MASK + 1> filter;
typedef struct element {
int val;
element *next;
} *lista;
lista h[mod];
void add(int x) {
filter[x & MASK] = true;
int key = x % mod;
lista p;
for (p = h[key]; p; p = p->next) {
if (p->val == x) {
return;
}
}
p = new element;
p->val = x;
p->next = h[key];
h[key] = p;
}
bool check(int x) {
if (filter[x & MASK] == false) {
return 0;
}
int key = x % mod;
for (lista p = h[key]; p; p = p->next) {
if (p->val == 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');
}
add(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;
}