Pagini recente » Cod sursa (job #2404932) | Cod sursa (job #829287) | Cod sursa (job #599442) | Cod sursa (job #3311012) | Cod sursa (job #531205)
Cod sursa(job #531205)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIMN 10000002
#define DIMC2 50002
#define DIMC 22
char S[DIMN], C[DIMC];
int LN, LC, NC, Ct;
unsigned int HS, HC[DIMC2], P = 1, P2;
int codif (char s[])
{
int h = 0;
for (int i = 0; i < LC; i++)
h = h * 3 + s[i] - 'a';
return h;
}
void elim_dubl ()
{
int i, j;
for (i = 1, j = 0; i <= NC; i++)
if (HC[i] != HC[i - 1])
HC[++j] = HC[i];
NC = j;
}
int cauta (int val)
{
int p = 0, u = NC, step = P2;
for (; step; step >>= 1)
if (p + step <= u && HC[p + step] <= val)
p += step;
return HC[p] == val;
}
int main ()
{
int i, p;
freopen ("abc2.in", "r", stdin);
freopen ("abc2.out", "w", stdout);
fgets (S, DIMN, stdin);
fgets (C, DIMC, stdin);
for (LN = 0; S[LN] >= 'a' && S[LN] <= 'c'; LN++);
for (LC = 0; C[LC] >= 'a' && C[LC] <= 'c'; LC++, P *= 3);
P /= 3;
HC[0] = codif (C);
while ( fgets (C, DIMC, stdin) )
HC[++NC] = codif (C);
sort (HC, HC + NC + 1);
elim_dubl ();
for (P2 = 1; P2 <= NC; P2 <<= 1);
P2 >>= 1;
LN = LN - LC + 1;
HS = codif (S);
if (cauta (HS))
Ct++;
for (i = 1; i < LN; i++)
{
HS = (HS - (S[i - 1]-'a') * P) * 3 + (S[i + LC - 1]-'a');
if (cauta (HS))
Ct++;
}
printf ("%d", Ct);
return 0;
}