Cod sursa(job #188731)

Utilizator scvrentScvrent Alexdrei scvrent Data 9 mai 2008 20:04:48
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <fstream>

using namespace std;

/* 
 * Cica pointeri sunt inceti,
 * Cica malloc mananca timp,
 * Cica, cica, cine stie?
 *
 * Un trie, dar c-un smen,
 * E scris in vector,
 * Unul mare. Ia trie[i][0]
 * Pentru primul fiu, trie[i][1]
 * Pentru al doilea iar trie[i][2]
 * Pentru celalalt.
 *
 * Si ce-i un cuvant?
 * O stare pentru care
 * Isword de stare este true
 *	     
 * 	    _	/// 
 *    \	   /_\	 | 
 *     )---|0|---| <--- un samurai
 *    /	   |_|	 ^
 *	 _/   \_  
 */	       	

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;
}