Pagini recente » Cod sursa (job #496356) | Cod sursa (job #77277) | Cod sursa (job #140626) | Cod sursa (job #279161) | Cod sursa (job #169287)
Cod sursa(job #169287)
#include <cstdio>
#include <cstring>
const int maxn = 10000002;
const int maxl = 30;
const int maxc = 50001;
const int mod1 = 128213;
const int mod2 = 128351;
const int pp1 = 73;
const int pp2 = 101;
FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");
char a[maxn];
int n, m;
char c[maxl];
int h1[mod1] = {0};
int h2[mod2] = {0};
int p1[maxl];
int p2[maxl];
int pow(int a, int b, int mod)
{
int s = 1;
for ( int i = 1; i <= b; ++i )
s *= a,
s %= mod;
return s;
}
void getnr()
{
int hash1 = 0, hash2 = 0;
for ( int i = 0; i < n; ++i )
{
hash1 = (hash1 + p1[i] * c[i]) % mod1;
hash2 = (hash2 + p2[i] * c[i]) % mod2;
}
h1[ hash1 ] = h2[ hash2 ] = 1;
}
int cnt;
int main()
{
fscanf(in, "%s", a);
m = strlen(a);
fscanf(in, "%s", c);
n = strlen(c);
for ( int i = 0; i < n; ++i )
p1[i] = pow(pp1, n - i - 1, mod1),
p2[i] = pow(pp2, n - i - 1, mod2);
//for ( int i = 0; i < n; ++i )
// printf("%d %d\n", p1[i], p2[i]);
getnr();
while ( fscanf(in, "%s", c) == 1 )
getnr();
int hash1 = 0, hash2 = 0;
for ( int i = 0; i < n; ++i )
{
hash1 = (hash1 + p1[i] * a[i]) % mod1;
hash2 = (hash2 + p2[i] * a[i]) % mod2;
}
if ( h1[ hash1 ] == 1 && h2[ hash2 ] == 1 )
++cnt;
for ( int i = n; i < m; ++i )
{
hash1 = ((hash1 - (a[i - n] * p1[0]) % mod1 + mod1) * pp1 + a[i]) % mod1;
hash2 = ((hash2 - (a[i - n] * p2[0]) % mod2 + mod2) * pp2 + a[i]) % mod2;
if ( h1[ hash1 ] == 1 && h2[ hash2 ] == 1 )
++cnt;
}
fprintf(out, "%d\n", cnt);
return 0;
}