統計難題

2019-11-11 05:15:32

字體：大中小

來源：轉載

供稿：網友

統計難題

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

bananabandbeeabsoluteacmbabbandabc Sample Output2310
解題報告：字典樹模板題，注意提交時用C++編譯器，G++會超時。
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;  //該字母出現的次數}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) //創建一棵字典樹{    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字符串為前綴的單詞的數量.{    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;}