hihocoder 1014: Trie树
原题链接：
http://hihocoder.com/problemset/problem/1014
算法分析
解决该题需要构造一个Trie类，用来对输入的每一个字符串进行统计。
该Trie类每个实例表示一个Trie树的节点，每个节点有26个“槽”，表示 'a'~'z' 的子节点。并且每个节点有一个计数器 count,用来表示经过该节点的字符串的数量，这样，当查询以某个字符串做前缀的词汇的个数的时候，直接借可以返回结果而无需深入查询。
C++算法实现如下：
#include<iostream>
using namespace std;
class Trie {
public:Trie() {count = 0;for (int i = 0; i < 27; i++) {child[i] = 0;}}~Trie() {for (int i = 0; i < 27; i++) {if (child[i] != 0) {delete child[i];//递归地调用子节点的析构函数，这样，只要释放了根节点，自然会释放其所有的子节点}}}void increse() {count++;}Trie* & operator[](int ch) {//获取子节点if (ch >= 'a'&&ch <= 'z') {return child[ch - 'a'];}else {return child[26];}}void insert(char * str) {//向字典中插入字符串if (str == 0) {return;}char * p = str;Trie* cur = this, *next;if (*p>='a'&&*p<='z') {increse();}while (*p >= 'a'&& *p <='z') {next = (*cur)[*p];if (next == 0) {next = (*cur)[*p] = new Trie();}next->increse();cur = next;p++;}}unsigned int query(char* str) {//查询字典中以该字符串为前缀的词汇的数量if (str == 0||*str=='\0') {return 0;}char* p = str;Trie* cur = this;while (*p != '\0') {if (*p<'a' || *p>'z') {return 0;}cur = (*cur)[*p];if (cur == 0) {return 0;}p++;}return cur->getCount();}unsigned int getCount() {return count;}private:Trie* child[27];unsigned int count;
};int main(int argc, char* argv[])
{Trie root;//根节点本身不代表任何字符int n;char str[11];char* p;cin >> n;cin.getline(str, 11);//输入n之后的换行符还在缓冲区里，要通过cin.getline()去除掉{ 这一 步操作会得到空行 }while (n-- > 0) {cin.getline(str, 11);root.insert(str);}int m;cin >> m;cin.getline(str, 11);//输入m之后的换行符还在缓冲区里，要通过cin.getline()去除掉{ 这一 步操作会得到空行 }while (m-- > 0) {cin.getline(str, 11);cout << root.query(str) << endl;}//C++编译器会自动地在main函数退出之前调用所有在栈中构造的类的析构函数,所以 root 的析构 函数会自动调用return 0;
}