POJ 2418 Hardwood Species 【Trie树】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

<题目链接>

题目大意：

给你一堆字符串，让你按字典序输出他们出现的频率.

解题分析：

首先，这是Trie数词频统计的题目，以Trie树的边储存字母，节点存储以该节点结尾的链所代表的字符串的数量，最后用dfs寻找Trie树中所有的单词，下面代码是用数组实现的Trie树。当然，本题也可用快排或者map直接水过。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = *;
const int SIZE = ; //ASCII中有128个常用字符
char str[];
int all;
struct Trie{
int ch[MAXN][SIZE];
int num[MAXN];
int pos; //sz为遍历到该节点的编号
void init(){
pos = ;
memset(ch[],,sizeof(ch[]));
}
int idx(char c){return c - ' ';} //因为本题的字符范围是所有字符，所以这里是减去字符中ASCII最小的 ' '(空格)
void insert(char *s){
int now = ,n = strlen(s);
for(int i=;i<n;i++){
int next = idx(s[i]);
if(!ch[now][next]){ //如果该节点没遍历过，那么就新建该节点
memset(ch[pos],,sizeof(ch[pos])); //注意这里是ch[pos],而不是ch[now]，因为now之前可能已经由其它的子节点了
ch[now][next] = pos++; //若该节点没被遍历过，给该节点编号
num[now] = ;
}
now = ch[now][next];
}
num[now]++;
}
void dfs(int u,int t){
str[t] = '\0'; //str[]存下该单词的每一位字符，虽然一开始就给每一位都赋'\0',但是如果该位置的字符符合要求，'\0'就会被该字符覆盖，不影响结果
if(num[u])printf("%s %.4f\n",str,(double)num[u]*/all); //如果遍历到前缀是完整单词的节点，则将该单词输出
for(int i = ;i < SIZE;i ++){
if(ch[u][i]){
str[t] = i+' '; //第t位存下该字符
dfs(ch[u][i],t+);
}
}
}
}word;
int main(){
word.init();
char s[];
all = ;
while(gets(s)){
if(s[]=='\0')break;
word.insert(s);
all++ ; //记录所有单词个数
}
word.dfs(,);
return ;
}

快排+map

#include <cstdio>
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e4+;
const int M = 1e6+;
map<string,int>mp;
vector<string>vec;int main(){
string str;
int cnt=;
while(getline(cin,str)){
if(!mp[str])vec.push_back(str);
mp[str]++;
cnt++;
}
sort(vec.begin(),vec.end());
for(int i=;i<vec.size();i++){
cout<<vec[i]<<" ";
printf("%.4lf\n",(mp[vec[i]]/cnt*1.0)*1.0*);
}
}