程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1251 (統計難題) 字典樹模板&&map實現

HDU 1251 (統計難題) 字典樹模板&&map實現

編輯：C++入門知識

HDU 1251 (統計難題) 字典樹模板&&map實現

【題目大意】：

Problem Description Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).

Input 輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.

注意:本題只有一組測試數據,處理到文件結束.

Output 對於每個提問,給出以該字符串為前綴的單詞的數量.

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

【字典樹模板】：

代碼：

/*
* Problem:HDU 1251
* Running time: 93MS
* Complier: G++
* Author: herongwei
* Create Time: 20:20 2015/10/27 星期二
*/
#include 
#include 
#include 
#include 
using namespace std;

const int maxn=4e5+10;
struct trie
{
    int sz;
    int ch[450000][26];
    int sum[4500000];
    trie(){sz=1;
    memset(ch,0,sizeof(ch));
    memset(sum,0,sizeof(sum));
    }
    int idx(char c){return c-'a';}
    void insert(char *s)
    {
        int u=0,n=strlen(s);
        for(int i=0; i

map映射： 
 
#include 
#include
#include 
#include 
#include 
using namespace std;
mapmp;
string s=;
int main()
{
    //freopen(1.txt,r,stdin);
    char ch;
    while(true){
        scanf(%c,&ch);
        if(ch=='
'){
            scanf(%c,&ch);
            s=;
        }
        s+=ch;
        if(ch=='
') break;
        mp[s]++;
    }
    while(cin>>s){
         printf(%d
,mp[s]);
    }
    return 0;
}