字典树
（以上的摘自百度百科~）
题目的意思：给出一些单词，让你统计以某个字符串为前缀的单词有多少个。
一开始，我用暴力来做，结果超时了。很明显，时间复杂度高。用字典树，可以高效的进行查找，减少无谓的字符的比较。
比如给出单词banana和band，生成的字典树应该是这样的：
每一个结点有一个长度为26的指针数组，可以连接每一个字母。如果再加如单词abc，则应该是这样的：
每一个结点有26个指针，，可以包含所以的单词。
下面是AC代码，有注释：
#include <iostream>#include <cstring>#include <string>using namespace std;class node{public:node* p[26];//指针数组int count;//以该结点为终点的前缀相同有多少个};node *root;//定义根节点void insert(char *str)//插入函数{int len = strlen(str);node* q = root, *p;for(int i = 0; i < len; i++) //遍历单词的字符串{int id = str[i] – 'a'; //表示第几个字符if(q->p[id] == NULL)//如果该字符不存在，增添一个结点{p = new node;p->count = 1;//初始化countfor(int j = 0; j < 26; j++) //初始化指针数组p->p[j] = NULL;q->p[id] = p;q = q->p[id];}else//该字符存在{q->p[id]->count++; //count自增就OK了q = q->p[id]; //指向下一个指针}}}node* finds(char *str)//查找函数{int len = strlen(str);node *q = root;for(int i = 0; i < len; i++){if(q->p[str[i] – 'a'] != NULL) //如果不为空，则该前缀存在q = q->p[str[i] – 'a'];elsereturn NULL;}return q;//返回该结点}int main(){root = new node;for(int i = 0; i < 26; i++)root->p[i] = NULL;root->count = 0;char str[15];while(1){gets(str);if(!str[0])//题目要求的是一个空行为标记，这里应该是这样的。break;//一开始以为是一个空格，WR了一次insert(str);}while(cin >> str){node *s = finds(str);if(s != NULL)//查找，不为空，则存在，输出该结点的count，printf("%d\n", s->count);elseprintf("0\n");//否则，不存在}return 0;}好久没有写过类似链表的操作了，有点生疏了~~
把你的脸迎向阳光，那就不会有阴影
