本文共 1164 字，大约阅读时间需要 3 分钟。
此题为Trie树（字典树）的模板题。
Trie树的概念、性质及讲解可参考该博客：本题采用了静态的模板，只用数组进行操作。
代码如下：#include#include #include #include using namespace std;const int maxn=1e6+5; //表示节点总数（要足够大）int Trie[maxn][26]; //Trie[i,j]表示第i个节点通过路径j到达的节点编号int num[maxn]={0}; //num[i]表示节点的属性（Trie数的节点是空的，其属性得依据题意来定），在此表示以该字符串为前缀的单词个数char s[11];int tot=1; //表示节点的个数void insert() //插入{ int len=strlen(s); int node=0; //node表示节点的编号，node=0，其实也就是根，从根开始搜索 int i,side; //side表示边（路径） for(i=0;i<=len-1;i++) { side=s[i]-'a'; if(Trie[node][side]==0) //等于0说明这个字母还没有插入，就得进行插入操作 Trie[node][side]=tot++; node=Trie[node][side]; //转换节点，继续搜索 num[node]++; //以该串为前缀的单词数+1 }}int inquire() //询问以某个串为前缀的单词数{ int len=strlen(s); int node=0; //依旧从根开始 int i,side; for(i=0;i<=len-1;i++) { side=s[i]-'a'; if(Trie[node][side]==0) //等于0就说明所建立的Trie树没有保存这个串，直接返回0即可 return 0; node=Trie[node][side]; //否则，转换节点，继续搜索 } return num[node]; }int main(){ int ans; while(gets(s)) //这里运用了一个输入的技巧，gets可以读取一个空行，且会把'\n'转化为'\0' { if(s[0]=='\0') break; insert(); } while(~scanf("%s",s)) { ans=inquire(); printf("%d\n",ans); } return 0;}
这道题要好好消化，很有帮助。今后还会写一下动态的模板（等我学会了。。。）
转载地址：http://yddci.baihongyu.com/