• Trie树

  ---

　　Trie树是一种用于实现字符串快速检索的多叉树结构。Trie的每个节点都拥有若干个字符指针，若在插入或检索字符串时扫描到一个字符c，就沿着当前节点的c字符指针，走向该指针指向的节点。

 

• 初始化

  ---

　　一棵空Trie仅包含一个根节点，该点的字符指针均指向空。

• 插入

  ---

　　当需要插入一个字符串S时，我们令一个指针P起初指向根节点。然后，依次扫描S中的每个字符c：

　　　　1.若P的c字符指针指向一个已经存在的节点Q，则令P = Q。

　　　　2.若P的c字符指针指向空，则新建一个节点Q，令P的c字符指针指向Q，然后令P = Q。

　　当S中的字符扫描完毕时，在当前节点P上标记它是一个字符串的末尾。

　       

• 检索

  ---

　　当需要检索一个字符串S在Trie是否存在时，我们令一个指针P起初指向根节点，然后依次扫描S中的每个字符ｃ：

　　　　１.若P的ｃ字符指针指向空，则说明S没有被插入过字典树，结束检索。

　　　　２.若P的ｃ字符指针指向一个已经存在的节点Q，则令P＝Q。

　　当S中的字符扫描完毕时，若当前节点P被标记为一个字符串的末尾，则说明S在字典树中存在，否则说明S没有被插入过。

1 int trie[N][26], val[N]; 2 int tot = 1; 3 void Insert(char* s) 4 { 5     int len = strlen(s), p = 1; 6     forn(k, len) 7     { 8         int ch = s[k] - 'a'; 9         if(trie[p][ch]==0)10             trie[p][ch] = ++tot;11         p = trie[p][ch];12     }13     val[p] = true;14 }15 bool　Search(char* s)16 {17     int len = strlen(s), p = 1;18     forn(k, len)19     {20         p = trie[p][s[k] - 'a'];21         if(p==0)22             return false;23     }24     return val[p];25 }