poj1056 （Trie入门）寻找字符串前缀

题意：给你一堆字符串，问是否满足对于任意两个字符串a、b，a不是b的前缀

字典树==前缀树==Trie树

trie入门题，只用到了insert和query操作

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 #define maxnode 1000
 6 #define sigma_size 30
 7 
 8 //struct Trie
 9 //{
10     int ch[maxnode][sigma_size];        //ch[i][j]：记录结点i的那个编号为j的子节点
11     int val[maxnode];                    //val[i]：i节点的附加信息，这里我们用来记录是否到一个单词的结束
12                                         //（即在trie树上root->i一路下来是否是一个完整的单词）
13     int sz;
14     void Trie()
15     {
16         sz=1;
17         memset(ch[0],0,sizeof(ch[0]));
18     }
19     int idx(char c)                       //idx(c)即字符c的编号。
20     {
21         return c-'0';                    //此处第一个字符是0所以return c-'0'
22     }
23     void Insert(string s,int v)
24     {
25         int u=0,n=s.length();
26         for (int i=0;i<n;i++)
27         {
28             int c=idx(s[i]);
29             if (!ch[u][c])
30             {
31                 memset(ch[sz],0,sizeof(ch[sz]));
32                 val[sz]=0;
33                 ch[u][c]=sz++;
34             }
35             u=ch[u][c];
36         }
37         val[u]=v;
38     }
39     bool query(string s)     //true:s is a prefix
40     {
41         int u=0,c;
42         for (int i=0;i<s.length();i++)
43         {
44             c=s[i]-'0';
45             if (!ch[u][c])    return false;
46 
47             u=ch[u][c];
48             if (val[u]==1)  return true;    //若此时s还没走完但trie树上已经走到结尾了，即树上单词是s的前缀
49         }
50         return true;
51     }
52 //};
53 
54 bool ok;
55 string str;
56 
57 int main()
58 {
59     //freopen("in.txt","r",stdin);
60 
61     ok=true;
62     Trie();
63     int num=0;
64     while (cin>>str)
65     {
66         if (str=="9")
67         {
68             num++;
69             if (ok)
70                 printf("Set %d is immediately decodable
",num);
71             else
72                 printf("Set %d is not immediately decodable
",num);
73             ok=true;
74             Trie();
75         }
76         else
77         {
78             if (query(str))
79                 ok=false;
80             Insert(str,1);
81         }
82     }
83 }

扩展：

1.用trie实现字符串排序？

直接对trie树前序遍历一遍即可

http://www.cnblogs.com/shuaiwhu/archive/2012/05/05/2484676.html

2.trie还有删除操作，不过实现比较麻烦。先mark一个

http://www.cnblogs.com/dolphin0520/archive/2011/10/11/2207886.html

3.trie在中文分词中的应用

http://blog.csdn.net/wzb56_earl/article/details/7902669