字典树（入门） 之 hdu 1075

第一次敲字典树还是在去年，就只做了一道，结果今年碰到几个字典树的题，结果都没做掉。

重新再学一遍。。。（这就是去年敲的那道题，又重新敲了一遍）

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX = 26;

struct Trie {
	Trie *next[MAX];
	char *c;
	Trie() {
		c = NULL;
		memset(next, NULL, sizeof(next));
	}
};

Trie *Root = new Trie;

void CreTrie(char *str, char *str1)
{
	int len = strlen(str);
	Trie *p = Root;
	for (int i = 0; i < len; ++i) {
		int pos = str[i] - 'a';
		if (NULL == p->next[pos]) {
			p->next[pos] = new Trie;
		}
		p = p->next[pos];
	}
	p->c = new char[10];
	strcpy(p->c, str1);
}

char* FinTrie(char *str) {
	int len = strlen(str);
	Trie *p = Root;
	for (int i = 0; i < len; ++i) {
		int pos = str[i] - 'a';
		if (NULL == p->next[pos]) {
			return str;
		}
		p = p->next[pos];
	}
	if (p->c != NULL) { return p->c; }
	return str;
}

void DelTrie(Trie *T)
{
	for (int i = 0; i < MAX; ++i) {
		if (T->next[i]) {
			DelTrie(T->next[i]);
		}
	}
	delete[] T;
}

bool Judge(char ch)
{
	if (ch >= 'a' && ch <= 'z') {
		return true;
	}
	else  {
		return false;
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	char str[3000], str1[10], str2[10];
	scanf("%s", str1);
	while (scanf("%s", str1) && 0 != strcmp(str1, "END")) {
		scanf("%s", str2);
		CreTrie(str2, str1);
	}
	scanf("%s", str1);
	getchar();
	while (gets(str) && 0 != strcmp(str, "END")) {
		char word[3000], ans[3000];
		memset(word, 0, sizeof(word));
		int len = strlen(str);
		int w_len = 0;
		for (int i = 0; i < len; ++i) {
			if (Judge(str[i])) { word[w_len++] = str[i]; }
			else {
				printf("%s", FinTrie(word));
				printf("%c", str[i]);
				w_len = 0;
				memset(word, 0, sizeof(word));
			}
		}
		printf("
");
	}
	DelTrie(Root);
	return 0;
}