Cod sursa(job #188725)

Utilizator scvalexAlexandru Scvortov scvalex Data 9 mai 2008 19:52:05
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <iostream>
#include <fstream>

using namespace std;

char text[10000001];
char cuv[21];
int trie[1000001][3];
bool isword[1000001];
int N = 2;
int R = 0;

void insert_into_trie(char *cuv)
{
	int state = 1;
	int next;
	for (char *c = cuv; *c; ++c) {
		next = *c - 'a';
		if (!trie[state][next])
			trie[state][next] = N++;
		state = trie[state][next];
	}
	isword[state] = true;
}

void walk_trie(char *text)
{
	int state = 1;
	int next;
	for (char *c = text; *c; ++c) {
		next = *c - 'a';
		if (!trie[state][next])
			break;
		state = trie[state][next];
		if (isword[state])
			++R;
	}
}

int main(int argc, char *argv[])
{
	FILE *fi = fopen("abc2.in", "r");
	fscanf(fi, "%s\n", text);
	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 << R << endl;
	fout.close();

	return 0;
}