Cod sursa(job #91425)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 12 octombrie 2007 15:07:04
Problema Abc2 Scor Ascuns
Compilator cpp Status done
Runda Marime 1.57 kb
// 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;
}