Cod sursa(job #91428)
// O( N * lungime_cuvant_mic^2 + lungime_text_mare )
// se construieste automatul finit asociat multimii de cuvinte mici (insa nu chiar in complexitatea optima)
#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], c[LMAX], w[NMAX][WLMAX];
int lw[NMAX];
int i, j, k, p, cuv, N, L, root, nstates, state;
int trie[MAX_STATES][3], dfa[MAX_STATES][3];
char final[MAX_STATES];
void df_trie(int state, int ncand, int *cand)
{
int p, q, nextstate;
int newncand, *newcand;
for (p = 0; p < 3; p++)
if (!dfa[state][p])
{
nextstate = root;
for (q = 0; q < ncand; q++)
if (trie[cand[q]][p] > 0)
{
nextstate = trie[cand[q]][p];
break;
}
dfa[state][p] = nextstate;
}
newcand = (int*) malloc((ncand + 1) * sizeof(int));
for (p = 0; p < 3; p++)
if (trie[state][p] > 0)
{
newncand = 0;
for (q = 0; q < ncand; q++)
if (trie[cand[q]][p] > 0)
newcand[newncand++] = trie[cand[q]][p];
newcand[newncand++] = root;
df_trie(trie[state][p], newncand, newcand);
}
free(newcand);
}
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(dfa, 0, sizeof(dfa));
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++;
dfa[state][w[cuv][i]] = trie[state][w[cuv][i]] = nstates;
}
state = trie[state][w[cuv][i]];
}
final[state] = 1;
for (p = 0; p < 3; p++)
trie[state][p] = dfa[state][p] = 0;
}
// construieste automatul corespunzator multimii de cuvinte
df_trie(root, 0, NULL);
// determina pozitiile candidat
memset(c, 0, sizeof(c));
state = root;
k = 0;
for (i = 0; i < L; i++)
{
s[i] -= 'a';
state = dfa[state][s[i]];
if (final[state])
k++;
}
fprintf(stderr, "%d\n", k);
freopen("abc2.out", "w", stdout);
printf("%d\n", k);
return 0;
}