統(tǒng)計(jì)難題

2019-11-11 06:07:32

字體：大中小

供稿：網(wǎng)友

統(tǒng)計(jì)難題

Time Limit: 4000/2000 MS (java/Others) Memory Limit: 131070/65535 K (Java/Others)Total Submission(s): 37320 Accepted Submission(s): 13799PRoblem DescriptionIgnatius最近遇到一個(gè)難題,老師交給他很多單詞(只有小寫字母組成,不會有重復(fù)的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計(jì)出以某個(gè)字符串為前綴的單詞數(shù)量(單詞本身也是自己的前綴). Input輸入數(shù)據(jù)的第一部分是一張單詞表,每行一個(gè)單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統(tǒng)計(jì)的單詞,一個(gè)空行代表單詞表的結(jié)束.第二部分是一連串的提問,每行一個(gè)提問,每個(gè)提問都是一個(gè)字符串.注意:本題只有一組測試數(shù)據(jù),處理到文件結(jié)束. Output對于每個(gè)提問,給出以該字符串為前綴的單詞的數(shù)量. Sample Input

bananabandbeeabsoluteacmbabbandabc Sample Output2310
解題報(bào)告：字典樹模板題，注意提交時(shí)用C++編譯器，G++會超時(shí)。
code：
#include<iostream>#include<stdio.h>#include<queue>#include<vector>#include<stack>#include<cstring>#include<algorithm>using namespace std;typedef long long ll;const int maxn=100005;const int MAX=26;typedef struct node{    struct node *next[MAX];    int flag;  //該字母出現(xiàn)的次數(shù)}Trie;Trie *root;/*root要初始化root=(Trie *)malloc(sizeof(Trie));root->flag=0;for(int i=0;i<MAX;i++){    root->next[i]=NULL;}*/void createTrie(char *str) //創(chuàng)建一棵字典樹{    int len = strlen(str);    Trie *p = root, *q;    for(int i=0; i<len; i++)    {        int id = str[i]-'a'; //小寫字母        if(p->next[id] == NULL)        {            q = (Trie *)malloc(sizeof(Trie));            q->flag = 0;            for(int j=0; j<MAX; j++)                q->next[j] = NULL;            p->next[id] = q;        }        p = p->next[id];        p->flag++;    }}int findTrie(char *str) //找出以str字符串為前綴的單詞的數(shù)量.{    int len = strlen(str);    Trie *p = root;    for(int i=0; i<len; i++)    {        int id = str[i]-'a';        p = p->next[id];        if(p == NULL)   //若為空集，表示不存以此為前綴的串            return 0;    }    return p->flag;}int main(){  //  freopen("input.txt","r",stdin);    root=(Trie *)malloc(sizeof(Trie)); //初始化    root->flag=0;    for(int i=0;i<MAX;i++){        root->next[i]=NULL;    }    char s[15];    while(gets(s)){        if(strlen(s)==0)            break;        createTrie(s);    }    while(~scanf("%s",s)){        printf("%d/n",findTrie(s));    }    return 0;}