学步园

1.字典树在串的快速检索中的应用。

给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

2. 字典树在“串”排序方面的应用

给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出
用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可

3. 字典树在最长公共前缀问题的应用

对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题（以后补上）。

AC代码：

#include<stdio.h>
#include<math.h>
#include<string.h>
struct node{
	char ch;
	char s[10];
	node *next[26];
	node()
	{
		ch='\0'; s[0]='\0';
		for(int i=0;i<26;i++)
			next[i] = NULL;
	}
};
node *root;
void insert(char *res,char *str)
{
	if(!root)
		root = new node;
	node *location = root;
	int len=strlen(str);
	for(int i=0;i<len;i++)
	{
		int num = str[i] - 'a';
		if(location->next[num] == NULL)
		{
			location->next[num] = new node;
			location->next[num]->ch=str[i];
		}
		location = location->next[num];
	}
	strcpy(location->s,res);
}
void search(char *str)
{
	int i,is_has=1;
	node *location = root;
	int len=strlen(str);
	for(i=0;i<len;i++)
	{
		int num = str[i] - 'a';
		if(location->next[num] == NULL)
		{
			printf("%s",str); is_has=0;break;
		}
		else
			location = location->next[num];
	}
	if(is_has==1)
	{
		if(location->s[0]!='\0') printf("%s",location->s);
		else printf("%s",str);
	}
}
int main()
{
	scanf("START\n");
	char s1[11],s2[3010];
	root=NULL;
	
	
	while(scanf("%s",s1)!=EOF)
	{
		if(s1[0]=='E') break;
		scanf("%s",s2);
		insert(s1,s2);
	}
	getchar();
	scanf("START\n");
	int c,ith=0; 
	while((c = getchar()) != 'E')
	{
		if (c >= 'a' && c <= 'z')  
			s2[ith++] = c;  
		else  
		{  
			s2[ith] = '\0';  
			if (ith != 0)  
				search(s2);  
			printf("%c", c); 
			ith = 0;  
		}  
	}
	return 0;
}

具体算法：

struct node
{
	bool isWord;
	node *next[26];
	node()
	{
		isWord = false;
		for(int i=0;i<26;i++)
			next[i] = NULL;
	}
};
class Trie
{
public:
	node *root;
	Trie(){root = NULL;}
	void insert(string str)
	{
		if(!root)
			root = new node;
		node *location = root;
		for(int i=0;i<str.length();i++)
		{
			int num = str[i] - 'a';
			if(location->next[num] == NULL)
			{
				location->next[num] = new node;
			}
			location = location->next[num];
		}
		location->isWord = true;
	}
	bool search(string str)
	{
		node *location = root;
		for(int i=0;i<str.length();i++)
		{
			int num = str[i] - 'a';
			if(location->next[num] == NULL)
				return false;
			location = location->next[num];
		}
		return location->isWord;
	}
};