Cod sursa(job #100291)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 12 noiembrie 2007 00:59:35
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 2.46 kb
// 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], ccand[WLMAX][WLMAX];
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 niv)
{
	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 = &ccand[niv];

	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, niv + 1);
		}
}

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, 0);

	// 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;
}