Pagini recente » Cod sursa (job #2296588) | Cod sursa (job #1985521) | Cod sursa (job #2479289) | Cod sursa (job #446352) | Cod sursa (job #615727)
Cod sursa(job #615727)
#include <cstdio>
#include <cstring>
#define MAXC 10000001
#define MOD 666013
char s[MAXC];
struct list
{
long long key;
list *next;
} *h[MOD];
unsigned cod(char *cuv)
{
unsigned c = 0;
int i;
for(i=0;i<strlen(cuv);++i)
{
c = c * 3 + cuv[i] - 'a';
}
return c;
}
void hash_insert(char *cuv)
{
list *node;
unsigned key = cod(cuv);
for(node=h[key%MOD];node;node=node->next)
{
if(node->key == key)
{
return;
}
}
node = new list;
node->key = key;
node->next = h[key%MOD];
h[key%MOD] = node;
}
int hash_count(int key)
{
list *node;
int nr = 0;
for(node = h[key%MOD]; node; node=node->next)
{
if(node->key == key)
{
++nr;
}
}
return nr;
}
int main()
{
int i, l, sol = 0;
char cuv[20];
unsigned key = 0;
unsigned r;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(s, MAXC, stdin);
while(fgets(cuv, 25, stdin))
{
if(cuv[strlen(cuv)-1] == '\n')
{
cuv[strlen(cuv)-1] = '\0';
}
hash_insert(cuv);
}
l = strlen(cuv);
r = 1;
for(i=l-1;i>=0;--i)
{
key = key * 3 + s[i] - 'a';
r *= 3;
}
r /= 3;
sol += hash_count(key);
for(i=1;i<strlen(s);++i)
{
key %= r;
key = key * 3 + s[i] - 'a';
sol += hash_count(key);
}
printf("%d\n", sol);
return 0;
}