Cod sursa(job #188473)

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

using namespace std;

const int TextLen = 10000000;

#define aToI(x) (*x - 'a')

char text[TextLen+1];
char cuv[21];

char trie[1000001][3];
bool isword[1000001];
int N(2);

int numwords(0);

void insert_into_trie(char *cuv)
{
	/*cout << "Inserting " << cuv << " into trie." << endl;*/
	int state = 1;
	for (char *c = cuv; *c; ++c) {
		if (!trie[state][aToI(c)])
			trie[state][aToI(c)] = N++;
		state = trie[state][aToI(c)];
	}
	isword[state] = true;
	trie[state][0] = trie[state][1] = trie[state][2] = 0;
	/*cout << "State " << state << " is a word." << endl;*/
}

void walk_trie(char *t)
{
	int state = 1;
	for (char *c = t; *c; ++c) {
		if (!trie[state][aToI(c)])
		    break;
		state = trie[state][aToI(c)];
		if (isword[state]) {
			++numwords;
			/*cout << "Found a word at state "  << state << endl;*/
		}
	}
}

int main(int argc, char *argv[])
{
	FILE *fi = fopen("abc2.in", "r");
	fscanf(fi, "%s\n", text);
	/*cout << text << endl;*/
	while (true) {
		cuv[0] = 0;
		fscanf(fi, "%s\n", cuv);
		if (!cuv[0])
			break;
		insert_into_trie(cuv);
	}
	fclose(fi);

	for (char *c = text; *c; ++c)
		walk_trie(c);

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

	return 0;
}