Pagini recente » Cod sursa (job #1764752) | Cod sursa (job #358676) | Cod sursa (job #1046963) | Cod sursa (job #1542999) | Cod sursa (job #167894)
Cod sursa(job #167894)
#include <cstdio>
#include <cstring>
const int maxn = 10000003;
const int maxcuv = 23;
const int base = 3;
const int hmod = 666013;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
//struct hash
//{
// char cuv[maxcuv];
// hash *next;
//};
char c[maxn];
//hash *h[hmod];
int h[hmod];
int pow(int x, int y)
{
if ( y == 0 )
return 1;
if ( y == 1 )
return x % hmod;
long long t = pow(x, y >> 1);
if ( (y & 1) )
return (long long)(((long long)(t * t) % hmod) * x) % hmod;
return (long long)(t * t) % hmod;
}
char buf[maxcuv];
//
//void add(int x, char cuv[])
//{
// hash *q = new hash;
//
// int i;
// for ( i = 0; cuv[i]; ++i )
// q->cuv[i] = cuv[i];
// q->cuv[i] = '\0';
//
// q->next = h[x];
// h[x] = q;
//}
int len;
void read()
{
fscanf(in, "%s", c);
int hh = 0;
while ( fscanf(in, "%s", buf) == 1 )
{
// fa hashul cuvantului
hh = 0;
int i;
for ( i = 0; buf[i]; ++i )
hh = hh + (buf[i] * pow(base, i)),
hh %= hmod;
len = i;
//add(hh, buf);
++h[ hh ];
//printf("%d\n", hh);
}
//printf("\n\n");
}
void solve()
{
int hh = 0;
int cnt = 0;
int n = strlen(c);
for ( int i = 0; i < n - len + 1; ++i )
{
hh = 0;
for ( int j = i; j < i + len; ++j )
hh = hh + (c[j] * pow(base, j - i)),
hh %= hmod;
//printf("%d\n", hh);
if ( h[ hh ] )
++cnt, h[ hh ] = 0;
}
fprintf(out, "%d\n", cnt);
}
int main()
{
read();
solve();
return 0;
}