Pagini recente » Cod sursa (job #1771132) | Cod sursa (job #95976) | Cod sursa (job #2486629) | Cod sursa (job #1219628) | Cod sursa (job #2831684)
#include <bits/stdc++.h>
inline void Open(const std::string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
const unsigned int MOD = 1572869;
std::vector <unsigned int> H[MOD + 1];
char s[10000001], word[21];
unsigned int len, Len, hash, ans, offset = 1;
int InH(unsigned int hash) {
unsigned int N = H[hash % MOD].size();
for(unsigned int i = 0;i < N;i++)
if(H[hash % MOD][i] == hash)
return 1;
return 0;
}
void addH(unsigned int hash) {
if(!InH(hash))
H[hash % MOD].emplace_back(hash);
}
void solve() {
std::cin >> s;
while(!std::cin.eof()) {
std::cin >> word;
len = strlen(word), hash = 0;
for(unsigned int i = 0;i < len;i++)
hash = (hash * 3 + (word[i] - 'a'));
addH(hash);
}
hash = 0;
for(unsigned int i = 0;i < len;i++) {
hash = hash * 3 + (s[i] - 'a');
offset *= 3;
}
offset /= 3, Len = strlen(s);
ans += InH(hash);
for(unsigned int i = len;i < Len;i++) {
hash = (hash - offset * (s[i - len] - 'a')) * 3 + (s[i] - 'a');
ans += InH(hash);
}
std::cout << ans;
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
Open("abc2");
int T = 1;
for(;T;T--) {
solve();
}
return 0;
}