hdu-统计难题-白红宇的个人博客

hdu-统计难题

发布日期：2022-02-02 02:58:02 浏览次数：8 分类：技术文章

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

Problem Description

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

Input

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

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

Output

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

Sample Input

bananabandbeeabsoluteacmbabbandabc

Sample Output

真心不会啊，真的感觉太难啦，这是别人的代码

一比较好的模板：

#define MAX 26typedef struct Trie{    Trie *next[MAX];//地址域    int v;//数据域};Trie *root;void createTrie(char *str){    int len=strlen(str);    Trie *p=root,*q;    for(int i=0; i
   
    next[id] == NULL)        {            q=(Trie *)malloc(sizeof(Trie));            q->v = 1;    //初始v==1            for(int j=0; j
    
     next[j]=NULL;            p->next[id]=q;            p=p->next[id];        }        else        {            p->next[id]->v++;            p = p->next[id];        }    }    p->v = -1;   //若为结尾，则将v改成-1表示}int findTrie(char *str){    int len = strlen(str);    Trie *p = root;    for(int i=0; i
     
      next[id];        if(p == NULL)   //若为空集，表示不存以此为前缀的串            return 0;        if(p->v == -1)   //字符集中已有串是此串的前缀            return -1;    }    return -1;   //此串是字符集中某串的前缀}int dealTrie(Trie* T){    int i;    if(T==NULL)        return 0;    for(i=0; i
      
       next[i]!=NULL)            deal(T->next[i]);    }    free(T);    return 0;}

代码：

#include
   
    #include
    
     #include
     
      using namespace std;char a[11];struct node{    int n;    struct node*a[26];    node()    {        n=1;        for(int i=0;i<26;i++)        a[i]=0;    }};node*root;void insert(string&s){    int i;    node*current=root;    for(i=0;i
      
       a[s[i]-'a']!=0)        {            current=current->a[s[i]-'a'];            current->n++;        }        else        {            node*code= new node();            current->a[s[i]-'a']=code;            current=code;        }    }}int find(string&s){    int i;    node*current=root;    for(i=0;i
       
        a[s[i]-'a']!=0)        {            current=current->a[s[i]-'a'];        }        else        return 0;    }   return current->n;}int main(){    int i,j,k;    root=new node();    string s;    int flag=1;    while(cin.getline(a,11))    {      s=a;      if(s!="")      {          if(flag)          insert(s);          else          printf("%d\n",find(s));      }      else      {          flag=0;      }    }    return 0;}

另：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;struct Trie{  int v;  Trie *next[26];};Trie root;void createTrie(char *str){    int len=strlen(str);    Trie *p=&root,*q;    for(int i=0;i
       
        next[id]==NULL)        {            q=(Trie *)malloc(sizeof(root));            q->v=1;            for(int j=0;j<26;j++)                q->next[j]=NULL;            p->next[id]=q;            p=p->next[id];        }        else        {            p->next[id]->v++;            p=p->next[id];        }    }}int findTrie(char *str){    int len=strlen(str);    Trie *p=&root;    for(int i=0;i
        
         next[id]; if(p==NULL) { return 0; } } return p->v;}int main(){ char str[15]; for(int i=0;i<26;i++) { root.next[i]=NULL; } while(gets(str)&&str[0]!='\0') { createTrie(str); } while(cin>>str) { int ans=findTrie(str); cout<
         
          <

转载地址：https://blog.csdn.net/u010368749/article/details/10009933 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：C/C++---随机数生成

下一篇：数据结构之---KMP算法讲解

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章