题意：给出一些数字串，判断是否有一个数字串是另一个串的前缀。
这题真的可以算是Trie树的一道模板题了。
先把Trie树建好，建树的时候记录一个sum表示一个节点有多少个串会包含此节点，然后再记录一个end表示这个节点是不是一个串的结尾。
然后dfs/bfs遍历整个Trie树若一个节点x满足end[x]=true && sum[x]>=2则题目条件成立。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
string s;
int trie[][];
int tot, sum[];
bool ennd[], ans;
void insert(string t) {
int p = ;
for (int i = ; i < (int)t.length(); i++) {
int k = t[i] - '';
sum[p]++;
if (!trie[p][k]) trie[p][k] = ++tot;
p = trie[p][k];
}
sum[p]++;
ennd[p] = ;
}
void dfs(int x) {
if (ennd[x] && sum[x] >= ) ans = ;
if (trie[x][]) {
dfs(trie[x][]);
}
if (trie[x][]) {
dfs(trie[x][]);
}
}
int case_num;
int main() {
while (cin >> s) {
case_num++;
if (s[] == '') continue;
ans = ;
tot = ;
memset(ennd, , sizeof(ennd));
memset(sum, , sizeof(sum));
memset(trie, , sizeof(trie));
insert(s);
while (cin >> s) {
if (s[] == '') break;
insert(s);
}
dfs();
if (ans) printf("Set %d is not immediately decodable\n", case_num);
else printf("Set %d is immediately decodable\n", case_num);
}
return ;
}