题目链接：http://poj.org/problem?id=1056
思路：
字典树的简单应用，就是判断当前所有的单词中有木有一个是另一个的前缀，直接套用模板再在Tire定义中加一个bool类型的变量用来判断当前到达的位置是否构成另一个单词的编码
代码：
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAX=;
class Trie
{
public:
bool isCode;
Trie *next[MAX];
};
bool flag; void Build_Tree(Trie *root,char *str)
{
Trie *p=root;
int i=;
while(str[i]!='\0')
{
if(p->next[str[i]-'']==NULL)
{
Trie *temp=new Trie;
for(int j=;j<MAX;j++)
temp->next[j]=NULL;
temp->isCode=false;
p->next[str[i]-'']=temp;
}
else
{
if(p->next[str[i]-'']->isCode)
{
flag=false;
return;
}
}
p=p->next[str[i]-''];
i++;
}
p->isCode=true; }
void del(Trie *root)
{
for(int i=;i<MAX;i++)
if(root->next[i]!=NULL)
del(root->next[i]);
free(root);
}
int main()
{
char str[];
int Case=;
while(scanf("%s",str)!=EOF)
{
Case++;
Trie *root=new Trie;
for(int i=;i<MAX;i++)
root->next[i]=NULL;
root->isCode=false;
flag=true;
Build_Tree(root,str);
while(scanf("%s",str))
{
if(strcmp(str,"")==)break;
if(flag) Build_Tree(root,str);
}
if(flag)cout<<"Set "<<Case<<" is immediately decodable"<<endl;
else cout<<"Set "<<Case<<" is not immediately decodable"<<endl;
del(root);
}
return ;
}