字典树 模板

建立字典树，求以……为前缀的单词个数

统计难题

问题描述：

lgnatius最近遇到一个难题，老师交给他很多单词（只有小写字符组成，不会有重复的单词出现），现在老师要他统计出以某个字符串为前缀的字符数量（单词本身也是自己的前缀）。

输入：

输入数据的第一部分是一张单词表，单词的长度不超过10，它们代表的是老师交给lgnatius统计的单词，一个空行代表单词表的结束。第二部分是一连串的提问，每行一个提问，每个提问都是字符串。

注意：本题只有一组测试数据，处理到文件结束

输出：

对于每个提问，给出以该字符串为前缀的单词数量。

Sample Input:

banana

band

bee

absolute

acm

ba

b

band

abc

Sample Output:

2

3

1

#include<cstdio>
#include<cstring>
using namespace std;
int n, m, ans;
char str[];
struct dic_tree  //构造字典树，26叉树，根节点为空
{
    dic_tree *node[]; //26个节点
    int num; // record the num of child
    bool terminal; //表示该结点位置是否是单词的结束位
    dic_tree()  // 构造函数，初始化终点情况与结点
    {
        for(int i; i<; ++i)
        {
            node[i] = NULL; // 初始化空结点， node[0]表示‘a’在单词中
            terminal = ;
            num = ;
        }
    }
}*root; //树是通过指针形式表达的

void build(dic_tree *p, char str[], int end) // 生成字典树的函数
{
    int ix = ;
    p->num++;
    while(ix < end)  // 循环直到读完单词最后一个字母
    {
        int c = str[ix] - 'a';
        if(p->node[c])  // 如果到node[c]连通
        {
            p = p->node[c];
            if(ix == end - )
                 p->terminal = ;
             ++ix;
        }
        else
        {
            p->node[c] = new dic_tree;  //如果不通，则在该结点生成一个26叉树
            p = p->node[c];
            if(ix == end - )
                 p->terminal = ;
             ++ix;
        }
        p->num++;
    }
}

int search(dic_tree *p, char str[], int end)
{
    int ix = ;
    while(ix < end)
    {
        int c = str[ix] - 'a';
        if(p->node[c])
        {
            p=p->node[c];
            if(ix == end-)
            {
                p->terminal = ;
                return p->num;
            }
            ++ix;
        }
        else return ;
    }
}

int main()
{
    // freopen("in.txt", "r", stdin);
    root = new dic_tree;
    while(gets(str)&&str[]!='/0')
    {
        bulid(root, str, strlen); // 生成字典树
    }
    while(scanf("%s", str) != EOF)
        printf("%d/n",search(root, str, strlen(str))); //搜索字典树
    return ;
}
           

当然，这道题还可以用map，只是时间较长：(^__^)

#include<iostream>  
#include<map>  
#include<string>  
using namespace std;  
int main()  
{  
    int i,j,k,len;  
    string str;char temp[],temp1[];  
    map <string,int> mymap;  
    while(gets(temp))  
    {  
        if(temp[]=='/n') break;  
        len=strlen(temp);  
        if(len==) break;  
        for(i=;i<len;i++)//求出某个字符串的所有前缀,并用MAP存起来  
        {  
            for(j=;j<=i;j++) temp1[j]=temp[j];temp1[j]='/0';  
            str.assign(temp1);  
            mymap[str]++;  
        }  
    }  
    while(scanf("%s",&temp)!=EOF)  
        cout<<mymap[temp]<<endl;//此时直接输出结果即可  
    return ;  
}