題目鏈接：http://poj.org/problem?id=1056
這道題用字典樹可接，具體思路就是每遇到一個單詞都把它插入到字典樹之中，然后如果遇到了9，就查詢每個單詞的詞尾標記的數(shù)量，如果詞尾標記的數(shù)量多于1，則證明另外一個單詞是這個單詞的前綴，輸出失敗，否則的話輸出成功。
view code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <vector>
5 using namespace std;
6 struct trie{
7 int ch[110][2];
8 int val[100];
9 int sz;
10 void reset(){
11 sz = 1; memset(ch[0], 0, sizeof(ch[0]));
12 memset(val, 0, sizeof(val));
13 }
14 int idx(char c){
15 return c - '0';
16 }
17 void insert(string s, int v){
18 int u = 0, n = s.size();
19 for (int i = 0; i < n; i++){
20 int c = idx(s[i]);
21 if (!ch[u][c]){
22 memset(ch[sz], 0, sizeof(ch[sz]));
23 val[sz] = 0;
24 ch[u][c] = sz++;
25 }
26 u = ch[u][c];
27 }
28 val[u] = v;
29 }
30 bool query(string s, int v){
31 int u = 0, n = s.size(), cnt = 0;
32 for (int i = 0; i < n; i++){
33 int c = idx(s[i]);
34 u = ch[u][c];
35 if (val[u] == v) cnt += 1;
36 }
37 if (cnt > 1) return 0;
38 return 1;
39 }
40 };
41 trie t;
42 string s;
43 vector<string> v;
44 int main(){
45 t.reset();
46 int p = 1;
47 while (cin >> s){
48 if (s.compare("9") == 0){
49 printf("Set %d is ", p++);
50 bool f = 1;
51 for (int i = 0; i < v.size(); i++)
52 if (!t.query(v[i], -1)){
53 f = 0; break;
54 }
55 if (!f) printf("not ");
56 printf("immediately decodable\n");
57 t.reset();
58 v.clear();
59 }
60 else{
61 v.push_back(s);
62 t.insert(s, -1);
63 }
64 }
65 return 0;
66 }
67