统计难题 HDU - 1251 (字典树)
程序员文章站
2022-04-17 21:21:57
...
题意:给出一组单词,然后再给出一组前缀,问这组单词拥有这组前缀的单词数量是多少?
题解:使用字典树,在insert函数中稍稍变形即可。
附上代码:
#include<bits/stdc++.h>
using namespace std;
const int maxnode=1e6+50;
const int sigma_size=26;
struct Trie{
int ch[maxnode][sigma_size];
int val[maxnode];
int sz;
void clear(){
sz=1;
memset(ch[0],0,sizeof(ch[0]));
memset(val,0,sizeof(val));
}
int idx(char c){
return c-'a';
}
void insert(string s){
int u=0,n=s.size();
for(int i=0;i<n;i++){
int c=idx(s[i]);
if(!ch[u][c]){
memset(ch[sz],0,sizeof(ch[sz]));
ch[u][c]=sz++;
}
u=ch[u][c];
val[u]++;
}
}
void find_prefixes(string s,int len,int &ans){
int u=0;
for(int i=0;i<len;i++){
if(s[i]=='\0'){
break;
}
int c=idx(s[i]);
if(!ch[u][c]){
return ;
}
u=ch[u][c];
}
ans=val[u];
}
};
Trie trie;
int main()
{
string s;
trie.clear();
while(getline(cin,s)){
if(s.size()==0){
break;
}
trie.insert(s);
}
while(getline(cin,s)){
int ans=0;
trie.find_prefixes(s,s.size(),ans);
cout<<ans<<endl;
}
return 0;
}
推荐阅读
-
hdu 1251(字典树) 统计偏题 http://acm.hdu.edu.cn/showproblem.php?pid=1251
-
HDU 6191 && 2017广西邀请赛:Query on A Tree(字典树启发式合并)
-
统计难题HDUOJ-1251(字典树统计前缀次数)
-
D - Phone List(hdu 1671) (字典树)
-
HDU-4825(数组维护字典树,更节省内存的写法)
-
HDU 1251 统计难题 Trie/字典树模版题
-
Trie字符串统计(字典树查询字符串出现次数)
-
Repository HDU - 2846 (字典树)
-
Problem C HDU - 5687(字典树的三种操作)
-
统计难题 HDU - 1251 (字典树)