Cod sursa(job #102193)

Utilizator octavOctavian Voicu octav Data 14 noiembrie 2007 03:29:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.12 kb
#include <stdio.h>
#include <stdlib.h>

#define MAXTEXT 10000000
#define MAXLEN 20

struct NODE {
	NODE *next[3];
	char q;
};

NODE *T;
char text[MAXTEXT + 1];

void trie_init() {
	T = (NODE*) calloc(1, sizeof(NODE));
}

void trie_add(char *word) {
	NODE *t;
	char *p;
	int ch;

	for(p = word, t = T; *p; p++) {
		ch = *p - 'a';
		if(!t->next[ch]) {
			t->next[ch] = (NODE*) calloc(1, sizeof(NODE));
		}
		t = t->next[ch];
	}
	t->q = 1;
}

NODE *trie_next(NODE *t, int ch) {
	if(!t->next[ch]) return NULL;
	else return t->next[ch];
}

int main() {
	NODE *t[MAXLEN];
	char word[MAXLEN + 1], *p;
	int i, count;

	freopen("abc2.in", "rt", stdin);
	freopen("abc2.out", "wt", stdout);

	gets(text);

	trie_init();
	while(scanf("%s", word) == 1) trie_add(word);

	for(i = 0; i < MAXLEN; i++) t[i] = NULL;

	count = 0;
	for(p = text; *p; p++) {
		for(i = 0; i < MAXLEN; i++) {
			if(!t[i]) break;
		}
		t[i] = T;
		for(i = 0; i < MAXLEN; i++) {
			if(t[i]) {
				t[i] = trie_next(t[i], *p - 'a');
				if(t[i] && t[i]->q) count++;
			}
		}
	}

	printf("%d\n", count);

	return 0;
}