trie樹的應用：查找hatword

Hat’s Words

Problem Description

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.You are to find all the hat’s words in a dictionary.

Input Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.Only one case. Output Your output should contain all the hat’s words, one per line, in alphabetical order. Sample Input a ahat hat hatword hziee word Sample Output ahat hatword 拿hatword，這個例子來說吧，這個單詞可以分成兩外兩個單詞，就是hat和word，hat是在我們給定的樣例中能找到的，同時word也能找到。那麼hatword這個單詞就符合要求。同時還可以察覺到，hat是hatword的一個字首，判斷一個單詞是不是另一個單詞的字首有很多辦法，一種是按順尋周遊第一個字元串，看所有字元在第二個字元串中是否出現而且順序與自身相同。還可以想到另外一種判斷方法，那就是字首樹即trie索引樹。前一種判斷的方法所所用的時間是O(N),二第二種方法可以在O(lgn)的時間内完成。如果我們對hat進行判斷，得到hat是hatword的字首，那麼剩下的就好辦了，把剩下的字元分離出來，作為獨立的一個單詞，然後在字典出中查找，如果找到，那麼說明hatword是滿足題目要求的單詞。下面給出分析的代碼：

#include<iostream>
#include<string.h>
using namespace std;
#define MAX_SIZE 26
typedef struct trie_node{
	bool is_terminated;
	char data;
	struct trie_node *child[MAX_SIZE];
}TrieNode, *TrieTree;
TrieNode *create_node(char c) {
	TrieNode *temp = (TrieNode*)malloc(sizeof(TrieNode));
	temp->is_terminated = false;
	temp->data = c;
	for(int i = 0;i < MAX_SIZE; i++)
		temp->child[i] = NULL;
	return temp;
}
void trie_insert(TrieTree *T, char *s) {
	TrieNode *p = *T;
	while(*s) {
		if(p->child[*s - 'a'] == NULL) {
			p->child[*s - 'a'] = create_node(*s);
		}
		p = p->child[*s - 'a'];
		s++;
	}
	p->is_terminated = true;
}
bool trie_search(TrieTree T, char *s) {
	TrieNode *p = T;
	while(p && *s) {
		if(p->child[*s - 'a'] == NULL) {
			return false;
		} else {
			p = p->child[*s - 'a'];
			s++;
		}
	}
	return (*s == '\0') && p->is_terminated;
}
bool find_hat_word(TrieTree T, char *s) {
	TrieNode *p = T;
	while(p && *s) {
		if(p->is_terminated) {
			if(trie_search(T, s)) {
				return true;
				break;
			}
		}
		p = p->child[*s - 'a'];
		s++;
	}
	return false;
}
void main() {
	TrieTree T = create_node(' ');
	char *s[]= {"a", "ahat", "hat", "hatword", "hziee", "word", "test", "case", "testcase"};
	int num = sizeof(s) /sizeof(char*);
	for(int i =0;i < num; i++)
		trie_insert(&T, s[i]);
	for(i = 0; i < num; i++)
		if(find_hat_word(T, s[i]))
			cout << s[i] << endl;
}