程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 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
2
3
1
0
【字典樹模板】:

 

代碼:

 

/*
* 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;
}


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved