题意：
给出多个串，如果没有一个串是别的串的前缀，则这些串是符合要求的，输出“Set * is immediately decodable”;
否则输出 "Set * is not immediately decodable";
输入中多个串以9表示输入结束
思路：
裸的字典树，先根据多个串建树，然后遍历每一个串看是否在字典树中..
Tips：
要注意找的时候应该判断是否为叶子结点，而不是仅仅判断是否在字典树中，因为建树的时候肯定存在该串..
Code：
1 #include <stdio.h> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 7 const int MAXN = 100010; 8 9 char arr[10][20], str[20]; 10 int next[MAXN][30]; 11 int tot; 12 void add(char *s) 13 { 14 int rt = 0; 15 for (int i = 0; s[i]; ++i) { 16 int a = s[i]-'0'; 17 if (next[rt][a] == 0) { 18 next[rt][a] = ++tot; 19 } 20 rt = next[rt][a]; 21 } 22 } 23 24 bool find(char *s) 25 { 26 int rt = 0; 27 for (int i = 0; s[i]; ++i) { 28 int a = s[i]-'0'; 29 if (next[rt][a] == 0) 30 return true; 31 rt = next[rt][a]; 32 } 33 for (int i = 0; i < 26; ++i) 34 if (next[rt][i] != 0) 35 return false; 36 return true; 37 } 38 39 int main() 40 { 41 // freopen("in.txt", "r", stdin); 42 bool flag = true; 43 int iCase = 1, cnt; 44 while (~scanf("%s", str)) { 45 flag = true; 46 memset(next, 0, sizeof(next)); 47 tot = cnt = 0; 48 while (strcmp(str, "9") != 0) { 49 strcpy(arr[cnt++], str); 50 add(str); 51 scanf("%s", str); 52 } 53 54 for (int i = 0; i < cnt; ++i) { 55 if (find(arr[i]) == false) { 56 flag = false; 57 break; 58 } 59 } 60 if (flag) printf("Set %d is immediately decodable\n", iCase++); 61 else printf("Set %d is not immediately decodable\n", iCase++); 62 } 63 return 0; 64 }