統(tǒng)計難題 (字典樹,val值統(tǒng)計經(jīng)過該點的字母數(shù)量)
題面:
統(tǒng)計難題
Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 25921????Accepted Submission(s): 10560
Problem Description
Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復(fù)的單詞出現(xiàn)),現(xiàn)在老師要他統(tǒng)計出以某個字符串為前綴的單詞數(shù)量(單詞本身也是自己的前綴).
?
Input
輸入數(shù)據(jù)的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統(tǒng)計的單詞,一個空行代表單詞表的結(jié)束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.
注意:本題只有一組測試數(shù)據(jù),處理到文件結(jié)束.
?
Output
對于每個提問,給出以該字符串為前綴的單詞的數(shù)量.
?
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
?
Sample Output
2
3
1
0
題意:
? ?額,中文大家都懂。
解題:
? ? 字典樹裸題,val值統(tǒng)計經(jīng)過該點的字母數(shù)量。
代碼:
#include#include#include#includeusing?namespace?std; struct?Trie { //用來儲存該節(jié)點的26個字母下標(biāo),ch的第一維要注意,要開大,不然會T? int?ch[1000010][26]; //val數(shù)組一般用來存儲權(quán)值,視題目靈活運用,sz是當(dāng)前節(jié)點數(shù)量 int?val[1000010],sz; //初始化 void?init() { sz=1; memset(ch[0],0,sizeof(ch[0])); } //插入一條單詞 void?insert(string?s) { //u是節(jié)點編號,并不是層數(shù) int?u=0,len=s.length(); for(int?i=0;i<len;i++) { //取下標(biāo) int?c=(s[i]-'a'); //如果該節(jié)點不存在,創(chuàng)建該節(jié)點 if(!ch[u][c]) { //真的是相當(dāng)?shù)氖? memset(ch[sz],0,sizeof(ch[sz])); //因為剛創(chuàng)建所以為1 val[sz]=1; //給該節(jié)點分配編號 ch[u][c]=sz++; //下移 u=ch[u][c]; } //已經(jīng)存在了 else { ??//下移,并計數(shù)值加一 ??u=ch[u][c]; ??????val[u]++; } } } //查詢前綴 int?query(string?s) { int?len=s.length(),u=0,c; //不斷下移,直至移到給定的前綴的最后一個單詞 bool?sign=true; for(int?i=0;i<len;i++) { ???c=s[i]-'a'; ???if(ch[u][c]) ?????????????u=ch[u][c]; ???????????else ???????????{ ??????????????sign=false; ??????????????break; ???????????} } if(sign) ??????????return?val[u]; ????????else ??????????return?0; } }; Trie?T; int?main() { ????????string?s; ????????T.init(); ????????while(getline(cin,s)) ????????{ ???????????if(s=="")break; ???????????T.insert(s); ????????} ????????while(getline(cin,s)) ????????{ ???????????cout<<T.query(s)<<endl; ????????} ????return?0; }