题目链接：https://vjudge.net/problem/POJ-1056
题意：给定一个字符串集，判断是否存在一个字符串是另一个字符串的前缀。
思路：和hdoj1671一样，有两种情况：
当前长度处已经存在字符串。比如先插入10，再插入101。
最后一个字符后面还有子结点。比如先插入101，再插入10。
AC code：
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std; const int maxn=1e6+;
int cas,trie[maxn][],key[maxn],cnt,flag;
char str[]; void insert(char *s){
int len=strlen(s),u=;
for(int i=;i<len;++i){
int t=s[i]-'';
if(!trie[u][t]){
++cnt;
memset(trie[cnt],,sizeof(trie[cnt]));
key[cnt]=;
trie[u][t]=cnt;
}
u=trie[u][t];
if(key[u]){
flag=;
return;
}
if(i==len-) key[u]=;
}
if(trie[u][]||trie[u][]) flag=;
} int main(){
while(~scanf("%s",str)){
flag=,cnt=;
memset(trie[],,sizeof(trie[]));
insert(str);
while(scanf("%s",str),str[]!='')
if(flag) insert(str);
if(flag) printf("Set %d is immediately decodable\n",++cas);
else printf("Set %d is not immediately decodable\n",++cas);
}
return ;
}