#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; } |
Double click to view unformatted code.