Hrbust_HR4995

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

字典树的模板题

连接：背单词

AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct Tire
{
    int nCount;
    Tire*next[26];
    Tire()
    {
        memset(next,0,sizeof(next));
        nCount=0;
    }
};
Tire *root;
void del(Tire*head)
{
    for(int i=0;i<26;i++)
        if(head->next[i]!=NULL)
        del(head->next[i]);
    delete head;
}
void Insert(char msg[])
{
    int i=0;
    Tire*cur=root;
    while(msg[i])
    {
        int k=msg[i]-'a';
        if(cur->next[k]==NULL)
            cur->next[k]=new Tire();
        cur=cur->next[k];
        cur->nCount++;
        i++;
    }
}
int FindTire(char msg[])
{
    int i=0;
    Tire *cur=root;
    while(msg[i])
    {
        int k=msg[i]-'a';
        if(cur->next[k]!=NULL)
            cur=cur->next[k];
        else
            return 0;
            i++;
    }
    return cur->nCount;
}
int main()
{
    root=new Tire();
    char tmp[18];
    while(true)
    {
        scanf("%s",tmp);
        if(strcmp(tmp,"END")==0)
            break;
        Insert(tmp);
    }
    while(scanf("%s",tmp)!=EOF)
    {
        printf("%d\n",FindTire(tmp));
    }
    del(root);
    return 0;
}