Pagini recente » Cod sursa (job #614001) | Cod sursa (job #2630615) | Cod sursa (job #2141665) | Cod sursa (job #1016678) | Cod sursa (job #167896)
Cod sursa(job #167896)
#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 )
{
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 ];
}
}
int exist(int hh, char cuv[])
{
hash *q = h[ hh ];
while ( q )
if ( strcmp(q->cuv, cuv) == 0 )
return 1;
return 0;
}
void solve()
{
int hh = 0;
int cnt = 0;
int n = strlen(c);
char cuv[maxcuv];
for ( int i = 0; i < n - len + 1; ++i )
{
hh = 0;
for ( int j = i; j < i + len; ++j )
cuv[j - i] = c[j],
hh = hh + (c[j] * pow(base, j - i)),
hh %= hmod;
if ( exist(hh, cuv) )
++cnt, h[ hh ] = NULL;
}
fprintf(out, "%d\n", cnt);
}
int main()
{
read();
solve();
return 0;
}