Cod sursa(job #188242)

Utilizator scvalexAlexandru Scvortov scvalex Data 7 mai 2008 16:01:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>
#include <fstream>

using namespace std;

/*
 * Un trie,
 * Dar nu ca altii,
 * Intr-un vector salvat,
 * Punctaj mare de luat.
 */

char s[10000001];
int L;
char w[50000][21];
int lw[50000], N;

int trie[1100000][3];
bool final[1100000];

int main(int argc, char *argv[])
{
	FILE *fi = fopen("abc2.in", "r");
	fscanf(fi, "%s", s);
	L = strlen(s);
	for (N = 0; ; ++N) {
		fscanf(fi, "%s", w[N]);

		if (!w[N][0])
			break;

		lw[N] = strlen(w[N]);
	}
	fclose(fi);

	int root = 1,
	    nstates = 1;

	int state;
	for (int cuv(0); cuv < N; ++cuv) {
		state = root;

		for (int i(0); i < lw[cuv]; ++i) {
			if (final[state])
				break;

			w[cuv][i] -= 'a';

			if (!trie[state][(int)w[cuv][i]]) {
				++nstates;
				trie[state][(int)w[cuv][i]] = nstates;
			}

			state = trie[state][(int)w[cuv][i]];
		}

		final[state] = true;

		for (int i(0); i < 3; ++i)
			trie[state][i] = 0;

		/*for (int i(0); i < lw[cuv]; ++i)
			cout << (char)(w[cuv][i] + 'a') << "\t";
		cout << endl;

		for (int i(0); i < nstates; ++i)
			cout << final[i] << "\t";
		cout << endl << endl;

		for (int i(0); i < 3; ++i) {
			for (int j(0); j < nstates; ++j)
				cout << trie[j][i] << "\t";
			cout << endl;
		}
		cout << endl;
		cout << "---" << endl;*/
	}

	int lc = lw[0];

	for (int i(0); i < L; ++i)
		s[i] -= 'a';

	int R(0);
	for (int i(0); i < L - lc + 1; ++i) {
		state = root;
		int j = i;
	      
		while ((state > 0) && !final[state]) {
			state = trie[state][(int)s[j]];
			++j;
		}

		if (final[state])
			++R;
	}

	ofstream fout("abc2.out");
	fout << R << endl;
	fout.close();

	return 0;
}