View Code of Problem 1466

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<map>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 300000;
int Tire[maxn][256];
int v[maxn];
char st[35];
int cnt = 1;
double n=0;
//建树,每输入一个单词到 s 里面就调用_insert()就好
void _insert(){
 	int root = 0;
 	for(int i=0;st[i];i++){
 		int next = st[i];
 		if(!Tire[root][next])
 			Tire[root][next] = ++cnt;
 		root = Tire[root][next];
 	}
 	v[root]++;//这里用了一个标记数组表示该点存在一个完整的单词,比如说`app`和`apple`
}
//int _find(char bufs[]){
// 	int root = 0;
// 	int next;
// 	for(int i=0;bufs[i];i++){
// 		next = bufs[i] - '0';
// 		root = Tire[root][next];
//// 		cout<<bufs[i]<<endl;
//		if(v[root]&&i!=strlen(bufs)-1){
//			return 0;
//		}
// 			
// 	}
// 	return 1;
//}
char bufs[100];
void dfs(int root,int len)
{	
	if(v[root])
		printf("%s %.4f\n",bufs,100*v[root]/n);
    int next;
	for(int i=0;i<256;i++){
 		if(Tire[root][i]!=0){
 			bufs[len] = i;
//				cout<<bufs[len]<<endl;
			dfs(Tire[root][i],len+1);
			bufs[len] = '\0';
		}
			
		
	}
//	cout<<bufs<<endl;
}

int main(){
	while(gets(st)){
		n++;
		_insert();
		
	}
	
	dfs(0,0);
	return 0;
}