题目：poj1056
题意：判断一个单词是否在其他单词中以前缀的形式存在
解答：建立字典树。在读到单词末尾的时候如果发现它已经有了，就返回false
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; const int sonnum = 3; int ok = 1; struct Trie { int num; bool terminal; struct Trie *son[sonnum]; }; Trie *NewTrie() { Trie *temp = new Trie; temp -> num = 1; temp -> terminal = false; for(int i = 0;i < sonnum;i++) temp -> son[i] = NULL; return temp; } void Insert(Trie *pnt,char *s,int len) { Trie *temp = pnt; for(int i = 0;i < len;i++) { if(temp -> son[s[i] - '0'] == NULL) temp -> son[s[i]-'0'] = NewTrie(); else temp -> son[s[i] - '0'] -> num++; temp = temp -> son[s[i] - '0']; } temp -> terminal = true; if(temp -> num > 1) ok = 0; return; } int main() { char a[10]; int num = 1; Trie *tree = NewTrie(); while(~scanf("%s",a)) { if(strlen(a) == 1 && a[0] == '9') { if(ok) printf("Set %d is immediately decodable\n",num++); else printf("Set %d is not immediately decodable\n",num++); Trie *tree = NewTrie(); ok = 1; continue; } Insert(tree,a,strlen(a)); } return 0; }