Pagini recente » Cod sursa (job #891527) | Cod sursa (job #2745316) | Cod sursa (job #1654806) | Cod sursa (job #155523) | Cod sursa (job #530953)
Cod sursa(job #530953)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define DIMN 10002
#define DIMC 22
char S[DIMN], C[DIMC];
int LN, LC, NC, FS[DIMN], Ct;
long long HS[DIMN], HC[DIMC], P = 1;
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, m;
while (p <= u)
{
m = p + (u - p) / 2;
if (HC[m] <= val)
p = m + 1;
else
u = m - 1;
}
return (u >= 0 && u <= NC) ? u : -1;
}
int main ()
{
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);
LN = LN - LC + 1;
HS[0] = codif (S);
for (int i = 1; i < LN; i++)
HS[i] = (HS[i - 1] - (S[i - 1]-'a') * P) * 3 + (S[i + LC - 1]-'a');
sort (HC, HC + NC + 1);
elim_dubl ();
for (int i = 0, p; i < LN; i++)
{
p = cauta (HS[i]);
if (p == -1) continue;
if (HC[p] == HS[i])
Ct++;
}
printf ("%d", Ct);
return 0;
}