Pagini recente » Cod sursa (job #368588) | Cod sursa (job #2110780) | Cod sursa (job #1694021) | Cod sursa (job #1421171) | Cod sursa (job #1502139)
#include <stdio.h>
#include <vector>
#include <cstring>
#define MOD 90907
using namespace std;
char s[10000010];
char word[21];
vector<unsigned int> table[MOD];
int search_table(unsigned int hash) {
unsigned int n = table[hash % MOD].size();
for(unsigned int i = 0; i < n; i++)
if(table[hash % MOD][i] == hash)
return 1;
return 0;
}
void add_to_table(unsigned int hash) {
if (!search_table(hash))
table[hash % MOD].push_back(hash);
}
int main(void) {
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
scanf("%s", s);
unsigned int i = 0;
unsigned int hash = 0;
unsigned int len;
while(!feof(stdin)) {
scanf("%s", word);
len = strlen(word);
hash = 0;
for(i = 0; i < len; i++)
hash = (hash * 3 + word[i] - 'a');
add_to_table(hash);
}
unsigned int sol = 0;
unsigned int offset = 1;
hash = 0;
for(i = 0; i < len; i++) {
hash = hash * 3 + s[i] - 'a';
offset *= 3;
}
offset /= 3;
sol += search_table(hash);
unsigned int slen = strlen(s);
for(i = len; i < slen; i++) {
hash = (hash - offset * (s[i - len] - 'a')) * 3 + s[i] - 'a';
sol += search_table(hash);
}
printf("%ld\n", sol);
return 0;
}