Cod sursa(job #101337)

Utilizator tvladTataranu Vlad tvlad Data 13 noiembrie 2007 13:36:37
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.17 kb
#include <cstdio>

class elem {
	elem* nx[3];
	bool fin;
public:
	elem() { nx[0] = nx[1] = nx[2] = NULL; fin = false; };
	elem*& operator[] ( char x ) { return nx[x-'a']; };
	bool word() { return fin; };
	void set_ok() { fin = true; };
	void erase() {
		if (nx[0]) {
			(*(nx[0])).erase();
			delete nx[0];
		}
		if (nx[1]) {
			(*(nx[1])).erase();
			delete nx[1];
		}
		if (nx[2]) {
			(*(nx[2])).erase();
			delete nx[2];
		}
	}
};

const int SM = 10000000;
const int CM = 20;

char s[SM+1];
char cuv[CM+1];
elem* root;

int main() {
	freopen("abc2.in","rt",stdin);
	freopen("abc2.out","wt",stdout);
	fgets(s,SM+1,stdin);
	root = new elem;
	elem* cur = root;
	while (!feof(stdin)) {
		scanf("%s\n",cuv);
		cur = root;
		for (int i = 0; cuv[i] != '\0' && !(*cur).word(); ++i) {
			if ((*cur)[cuv[i]] == NULL) (*cur)[cuv[i]] = new elem;
			cur = (*cur)[cuv[i]];
		}
		(*cur).set_ok();
	}
	int r = 0;
	for (int i = 0; s[i] != '\n'; ++i) {
		cur = root;
		for (int j = i; s[j] != '\n'; ++j) {
			if ((*cur)[s[j]] == NULL) break;
			cur = (*cur)[s[j]];
			if ((*cur).word()) {
				++r;
				break;
			}
		}
	}
	printf("%d\n",r);
	return 0;
}