Pagini recente » Cod sursa (job #1404870) | Cod sursa (job #2291213) | Cod sursa (job #567396) | Cod sursa (job #2807719) | Cod sursa (job #219668)
Cod sursa(job #219668)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
char s[10000005], cuv[25];
int rez, p[25], w[50005], n, k;
int hash[10000][10];
void add(int x)
{
int poz = x % 9997, i, ok;
if (!hash[poz][0])
{
hash[poz][0]++;
hash[poz][1] = x;
}
else
{
ok = 1;
for (i = 1; i <= hash[poz][0]; i++) if (hash[poz][i] == x) ok = 0;
if (ok) hash[poz][++hash[poz][0]] = x;
}
}
int cauta(int x)
{
int poz = x % 9997;
for (int i = 1; i <= hash[poz][0]; i++) if (hash[poz][i] == x) return 1;
return 0;
}
int cmp(const void *i, const void *j)
{
return *(int*)i - *(int*)j;
}
void putere()
{
int i;
p[0] = 1;
for (i = 1; i <= 20; i++) p[i] = p[i - 1] * 3;
}
int transform(char s[], int n)
{
int x = 0, i;
for (i = 0; i < n; i++) x += (s[i] - 'a') * p[n - i - 1];
return x;
}
int caut(int x)
{
int p, u, m, cnt = 0;
p = 0; u = n - k + 1;
while (p <= u)
{
m = (p + u) / 2;
if (w[m] == x) break;
if (w[m] < x) p = m + 1;
else u = m - 1;
}
if (p > u) return 0;
while (w[m] == x) m--;
m++;
for (; w[m] == x; m++) cnt++;
return cnt;
}
int main()
{
freopen("abc2.in","r",stdin);
freopen("abc2.out","w",stdout);
int i, j, x;
putere();
fgets(s,10000001,stdin);
fgets(cuv,25,stdin);
k = strlen(cuv) - 1;
n = strlen(s) - 1;
x = 0;
for (i = 0; i < k; i++) x += (s[i] - 'a') * p[k - i - 1];
w[0] = x;
for (; i < n; i++)
{
x -= ((s[i - k] - 'a') * p[k - 1]);
x *= 3;
x += (s[i] - 'a');
w[i - k + 1] = x;
}
qsort(w,n - k + 1,sizeof(int),cmp);
x = transform(cuv, k);
add(x);
rez += caut(x);
while (!feof(stdin))
{
fgets(cuv,25,stdin);
x = transform(cuv,k);
if (!cauta(x))
{
rez += caut(x);
add(x);
}
}
printf("%d\n",rez);
return 0;
}