Pagini recente » Cod sursa (job #2826603) | Cod sursa (job #79414) | Cod sursa (job #1919454) | Cod sursa (job #316601) | Cod sursa (job #531198)
Cod sursa(job #531198)
#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;
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 ()
{
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 ();
LN = LN - LC + 1;
HS = codif (S);
p = cauta (HS);
if (p != -1)
if (HC[p] == HS)
Ct++;
for (i = 1; i < LN; i++)
{
HS = (HS - (S[i - 1]-'a') * P) * 3 + (S[i + LC - 1]-'a');
p = cauta (HS);
if (p != -1)
if (HC[p] == HS)
Ct++;
}
printf ("%d", Ct);
return 0;
}