Pagini recente » Cod sursa (job #2134866) | Cod sursa (job #988837) | Cod sursa (job #3126233) | Cod sursa (job #717048) | Cod sursa (job #169727)
Cod sursa(job #169727)
#include <cstdio>
#include <cstring>
const int maxn = 10000002;
const int maxl = 22;
const int maxc = 50001;
const int mod1 = 1 << 18;
const int mod2 = 1 << 17;
const int pp1 = 3;
const int pp2 = 73;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
struct hash
{
unsigned short poz;
hash *next;
};
char a[maxn];
int n, m;
char c[maxc][maxl];
int hsh[maxc];
unsigned char h1[(mod1 >> 3) + 1];
unsigned char h2[(mod2 >> 3) + 1];
hash *l[mod1];
int p1[maxl];
int p2[maxl];
void add(int where, unsigned short what)
{
hash *q = new hash;
q->poz = what;
q->next = l[where];
l[where] = q;
}
int pow(int a, int b, int mod)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s *= a,
s = s & (mod - 1);
return s;
}
int j = 1;
void getnr()
{
int hash1 = 0, hash2 = 0;
for ( int i = 0; i < n; ++i )
{
hash1 = (hash1 + p1[i] * c[j][i]) & (mod1 - 1);
hash2 = (hash2 + p2[i] * c[j][i]) & (mod2 - 1);
}
h1[ hash1 >> 3 ] |= (1 << (hash1 & 7));
h2[ hash2 >> 3 ] |= (1 << (hash2 & 7));
add(hash1, j);
hsh[j] = hash2;
}
char t[maxl];
inline int mystrcmp(char x[], char y[])
{
for ( int i = 0; y[i]; ++i )
if ( x[i] != y[i] )
return 0;
return 1;
}
int check(int what, int wwhat, int from, int to)
{
for ( int i = from; i <= to; ++i )
t[i - from] = a[i];
t[to - from + 1] = '\0';
hash *q = l[what];
for ( ; q; q = q->next )
if ( hsh[ q->poz ] == wwhat )
if ( mystrcmp(c[ q->poz ], t) )
return 1;
return 0;
}
int cnt;
int main()
{
//fscanf(in, "%s", a);
fgets(a, sizeof(a), in);
m = strlen(a) - 1;
//fscanf(in, "%s", c[1]);
fgets(c[1], 32, in);
n = strlen(c[1]) - 1;
for ( int i = 0; i < n; ++i )
p1[i] = pow(pp1, n - i - 1, mod1),
p2[i] = pow(pp2, n - i - 1, mod2);
getnr();
++j;
while ( fgets(c[j], 32, in) )
getnr(), ++j;
unsigned int hash1 = 0, hash2 = 0;
for ( int i = 0; i < n; ++i )
{
hash1 = (hash1 + p1[i] * a[i]) & (mod1 - 1);
hash2 = (hash2 + p2[i] * a[i]) & (mod2 - 1);
}
if ( ( h1[ hash1 >> 3 ] & (1 << (hash1 & 7)) ) && ( h2[ hash2 >> 3 ] & (1 << (hash2 & 7)) ) )
if ( check(hash1, hash2, 0, n - 1) )
++cnt;
int ph1 = p1[0], ph2 = p2[0];
for ( int i = n; i < m; ++i )
{
hash1 = ((hash1 - ((a[i - n] * ph1) & (mod1 - 1)) + mod1) * pp1 + a[i]) & (mod1 - 1);
hash2 = ((hash2 - ((a[i - n] * ph2) & (mod2 - 1)) + mod2) * pp2 + a[i]) & (mod2 - 1);
if ( ( h1[ hash1 >> 3 ] & (1 << (hash1 & 7)) ) && ( h2[ hash2 >> 3 ] & (1 << (hash2 & 7)) ) )
if ( check(hash1, hash2, i - n + 1, i) )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}