Pagini recente » Cod sursa (job #2805889) | Cod sursa (job #2649035) | Cod sursa (job #297436) | Cod sursa (job #2402770) | Cod sursa (job #91425)
Cod sursa(job #91425)
// O(lungime_cuvant_mic * lungime_text)
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define LMAX 10000100
#define NMAX 50100
#define WLMAX 30
#define MAX_STATES 1100000
char s[LMAX], w[NMAX][WLMAX];
int lw[NMAX];
int i, j, k, p, cuv, N, L, lc, root, nstates, state;
int trie[MAX_STATES][3];
char final[MAX_STATES];
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++;
}
// construieste trie-ul corespunzator multimii de cuvinte
root = nstates = 1;
memset(trie, 0, sizeof(trie));
memset(final, 0, sizeof(final));
for (cuv = 0; cuv < N; cuv++)
{
state = root;
for (i = 0; i < lw[cuv]; i++)
{
if (final[state])
break;
w[cuv][i] -= 'a';
if (!trie[state][w[cuv][i]])
{
nstates++;
trie[state][w[cuv][i]] = nstates;
}
state = trie[state][w[cuv][i]];
}
final[state] = 1;
for (p = 0; p < 3; p++)
trie[state][p] = 0;
}
// determina pozitiile candidat
lc = lw[0];
for (i =0; i < L; i++)
s[i] -= 'a';
k = 0;
for (i = 0; i < L - lc + 1; i++)
{
state = root;
j = i;
while (state > 0 && !final[state])
{
state = trie[state][s[j]];
j++;
}
if (final[state])
k++;
}
fprintf(stderr, "%d\n", k);
freopen("abc2.out", "w", stdout);
printf("%d\n", k);
return 0;
}