Cod sursa(job #91427)

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