統計難題

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 53007????Accepted Submission(s): 18515

?

Problem Description

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

?

?

Input

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

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

?

?

Output

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

?

?

Sample Input

banana band bee absolute acm ba b band abc

?

?

Sample Output

2 3 1 0

#include<bits/stdc++.h> using namespace std;int trie[400001][26],len,root,tot,sum[400001]; bool p; int n,m; char s[11]; void insert() {len=strlen(s);root=0;for(int i=0;i<len;i++){int id=s[i]-'a';if(!trie[root][id]) trie[root][id]=++tot;sum[trie[root][id]]++;//前綴后移一個位置保存 root=trie[root][id];} } int search() {root=0;len=strlen(s);for(int i=0;i<len;i++){int id=s[i]-'a';if(!trie[root][id]) return 0;root=trie[root][id];}//root經過此循環后變成前綴最后一個字母所在位置的后一個位置 return sum[root];//因為前綴后移了一個保存，所以此時的sum[root]就是要求的前綴出現的次數 }int main() {int f=0;while(gets(s)){if(strlen(s)==0){f=1;continue;}if(!f)insert();else cout<<search()<<endl;}return 0; }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu-1251（基本字典树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。