统计难题 HDU - 1251（字典树）-白红宇

统计难题 HDU - 1251（字典树）

阅读量：4558 次

发布时间：2019-06-08

本文共 1337 字，大约阅读时间需要 4 分钟。

统计难题 HDU - 1251

题目链接：

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

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

注意:本题只有一组测试数据,处理到文件结束.

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

Sample Input

bananabandbeeabsoluteacmbabbandabc

Sample Output

2310 思路：字典树模板

// // Created by HJYL on 2019/8/17.//#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  using namespace std;typedef long long ll;const int maxn=1e6+10;char str[maxn];struct trie{ trie* next[26]; int sum; trie(){ for(int i=0;i<26;i++) { next[i]=NULL; } sum=0; }}root;void insert(char* s){ trie* p=&root; for(int i=0;s[i];i++) { if(p->next[s[i]-'a']==NULL) { p->next[s[i]-'a']=new trie; } p=p->next[s[i]-'a']; p->sum++; }}int find(char* s){ trie* p=&root; for(int i=0;s[i];i++) { if(p->next[s[i]-'a']==NULL) return 0; else p=p->next[s[i]-'a']; } return p->sum;}int main(){ //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text","r",stdin); while(gets(str)&&str[0]!='\0') { insert(str); } while(scanf("%s",str)==1) { printf("%d\n",find(str)); } return 0;}

转载于:https://www.cnblogs.com/Vampire6/p/11370882.html

你可能感兴趣的文章