Pagini recente » Cod sursa (job #761255) | Cod sursa (job #3253404) | Cod sursa (job #1478018) | Cod sursa (job #866703) | Cod sursa (job #622251)
Cod sursa(job #622251)
#include <cstdio>
#include <cstring>
#define MAXC 10000001
#define MAXCUV 22
#define MOD 666013
char s[MAXC];
int l;
struct list
{
long long key;
list *next;
} *h[MOD];
unsigned cod(char *cuv)
{
unsigned c = 0;
int i;
for(i=0;i<l-1;++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(unsigned 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, sol = 0, last, ls;
char cuv[MAXCUV];
unsigned key = 0;
unsigned r;
freopen("abc2.in", "r", stdin);
freopen("abc2.out", "w", stdout);
fgets(s, MAXC, stdin);
fgets(cuv, MAXCUV, stdin);
l = strlen(cuv);
last = 0;
do
{
++last;
if(cuv[l-1] == '\n')
{
cuv[l-1] = '\0';
}
hash_insert(cuv);
} while(fgets(cuv, MAXCUV, stdin));
if(last > 1) --l;
r = 1;
for(i=0;i<l;++i)
{
key = key * 3 + s[i] - 'a';
r *= 3;
}
r /= 3;
if(r == 0)
{
r = 1;
}
sol += hash_count(key);
ls = strlen(s);
for(i=l;i<ls;++i)
{
key %= r;
key = key * 3 + s[i] - 'a';
sol += hash_count(key);
}
printf("%d\n", sol);
return 0;
}