Pagini recente » Cowfood | Rating Pruteanu Theodor (cyg_Theo) | Cod sursa (job #851825) | Cod sursa (job #798090) | Cod sursa (job #91424)
Cod sursa(job #91424)
// O( lungime_text_mare * N * lungime_cuvant_mic ) -> KMP pt fiecare cuvant mic
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LMAX 10000100
#define NMAX 50100
#define WLMAX 30
char s[LMAX], c[LMAX], w[NMAX][WLMAX];
int lw[NMAX], p[WLMAX];
int i, j, k, cuv, N, L;
int main()
{
freopen("abc2.in", "r", stdin);
s[0] = 0;
fgets(s, LMAX - 1, stdin);
s[strlen(s) - 1] = 0;
L = strlen(s);
N = 0;
while (1)
{
w[N][0] = 0;
fgets(w[N], WLMAX - 1, stdin);
if (!w[N][0])
break;
w[N][strlen(w[N]) - 1] = 0;
lw[N] = strlen(w[N]);
N++;
}
memset(c, 0, sizeof(c));
for (cuv = 0; cuv < N; cuv++)
{
// calculeaza functia prefix de la KMP
p[0] = k = -1;
for (i = 1; i < lw[cuv]; i++)
{
while (w[cuv][i] != w[cuv][k + 1] && k >= 0)
k = p[k];
if (w[cuv][i] == w[cuv][k + 1])
k++;
p[i] = k;
}
// cauta cuvantul cuv in sirul mare
k = -1;
for (i = 0; i < L; i++)
{
while (s[i] != w[cuv][k + 1] && k >= 0)
k = p[k];
if (s[i] == w[cuv][k + 1])
k++;
if (k == lw[cuv] - 1)
{
c[i - lw[cuv] + 1] = 1;
k = p[k];
}
}
}
k = 0;
for (i = 0; i < L; i++)
if (c[i])
k++;
fprintf(stderr, "%d\n", k);
freopen("abc2.out", "w", stdout);
printf("%d\n", k);
return 0;
}