题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1251
样例:
最简单的单词插入,来建立字典树
字典树的本质是模仿人查字典的时候依次检索的过程
#include <iostream> #include <string> #include <stdio.h> #include <cstring> using namespace std; int tree[1000100][26];//用来记录字典树当前字母的位置 int num[1000100];//记录以某一字符串为前缀的单词数量 int pos = 1;//当前新分配的存储位置,把每个树枝节点都用pos用一个数字表示 void insert(char s[]) { int p = 0;//当前位置(最起始) for (int i = 0; i < strlen(s); i++) { int n = s[i] - 'a';//把字母数字化 if (tree[p][n] == 0)//如果对应的字符还没有值 { pos++;//更新pos,创建一个新的位子表示这个分支 tree[p][n] = pos;//tree中记录 } p = tree[p][n];//把下一次访问位置改为tree[p][n]的 num[p]++;//计数,经过了这里几次 } } int count(char s[]) { int p = 0; for (int i = 0; i < strlen(s); i++) { int n = s[i] - 'a'; if (tree[p][n] == 0)//要查找的前缀有一个字母在字典树中没有出现过,说明查无此字符 { return 0; } p = tree[p][n];//逐渐深入字典树 } return num[p];//检索完前缀后,输出最后一个前缀字母的num } int main() { char s[20]; while (gets(s)) { if (!strlen(s)) break;//为0说明输入的是空行 insert(s); } while (gets(s)) { cout << count(s) << endl; } return 0; }