Pagini recente » Cod sursa (job #1127618) | Cod sursa (job #3196501) | Cod sursa (job #833445) | Cod sursa (job #1220873) | Cod sursa (job #2298074)
#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
const int MAX_LENGTH = 10000000;
const int MOD = 10041;
char s[MAX_LENGTH + 1];
char word[MAX_LENGTH + 1];
std::vector<unsigned int> foundHash[MOD];
int main() {
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
scanf("%s", s);
int n = (int)strlen(s);
int lWord = 0;
while (scanf("%s", word) != EOF) {
lWord = (int)strlen(word);
unsigned int hash = 0;
for (int i = 0; i < lWord; i++)
hash = hash * 3 + (word[i] - 'a');
bool ok = true;
for (auto it : foundHash[hash % MOD]) {
if (it == hash) {
ok = false;
break;
}
}
if (ok)
foundHash[hash % MOD].push_back(hash);
}
unsigned int pow = 1;
for (int i = 1; i < lWord; i++)
pow *= 3;
unsigned int hash = 0;
for (int i = 0; i < lWord; i++)
hash = hash * 3 + (s[i] - 'a');
int ans = 0;
for (auto it : foundHash[hash % MOD]) {
if (it == hash) {
ans++;
break;
}
}
for (int i = lWord; i < n; i++) {
hash -= pow * (s[i - lWord] - 'a');
hash = hash * 3 + (s[i] - 'a');
for (auto it : foundHash[hash % MOD]) {
if (it == hash) {
ans++;
break;
}
}
}
printf("%d\n", ans);
return 0;
}