Cod sursa(job #189155)

Utilizator scvalexAlexandru Scvortov scvalex Data 12 mai 2008 16:43:38
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <iostream>
#include <fstream>

using namespace std;

/* 
 * Asta-i cica Corasick-Aho,
 * Si-o suta ar-trebui sa ia.
 *
 * Foloseste un trie optimizat,
 * Care nu-i altul decat Knuth-Morris-Pratt,
 * In n patrat.
 */	       	

char text[10000001];
char cuv[21];
int trie[1000001][3];
int nextn[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++;
		nextn[state][next] = trie[state][next];
		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';

		state = nextn[state][next];

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

void build_nextn(int state, int *cand, int ncand)
{
	/* cout << "Sunt la " << state << endl;
	for (int i(0); i < ncand; ++i)
		cout << cand[i] << " ";
	cout << endl; */

	for (int i(0); i < 3; ++i)
		if (!nextn[state][i]) {
			int nextstate = 1;

			for (int j(0); j < ncand; ++j)
				if (trie[cand[j]][i]) {
					nextstate = trie[cand[j]][i];
					break;
				}

			nextn[state][i] = nextstate;
		}

	int *newcand = new int[ncand+1];
	int newncand = 0;

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

			for (int j(0); j < ncand; ++j)
				if (trie[cand[j]][i])
					newcand[newncand++] = trie[cand[j]][i];
			newcand[newncand++] = 1;

			build_nextn(trie[state][i], newcand, newncand);
		}

	delete newcand;
}

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

	build_nextn(1, 0, 0);

	walk_trie(text);

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

	return 0;
}