国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

統計難題

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 Output
2310

解題報告:字典樹模板題,注意提交時用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;}


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 镇雄县| 修文县| 革吉县| 罗平县| 米泉市| 吉木萨尔县| 涟源市| 乌什县| 莱阳市| 交口县| 十堰市| 阳西县| 英德市| 寿阳县| 正定县| 墨玉县| 黎川县| 延边| 黄平县| 马鞍山市| 玉田县| 宁远县| 神木县| 洮南市| 宜阳县| 仁化县| 雷山县| 仙桃市| 巴青县| 浦江县| 广灵县| 平利县| 宁波市| 普定县| 凉城县| 泸州市| 吉木萨尔县| 运城市| 阿鲁科尔沁旗| 明光市| 兴宁市|