就是给你n个（1000000）字符串，这些字符串一共最多m（10000）种，一个字符串最长30个字符。问你每种字符串占总数的百分比。
注：这个有点坑的地方就是，字符串除了大小写字母，还好有多未知的字符，所有字典树数组开成了270就过了，之前开的100大小就过不去。
#include<iostream> #include<stdio.h> #include<string.h> #define M 10500 using namespace std; int num[M]={0}; char str[M][35]={0}; struct trie { int id; trie *next[270]; trie() { id=0; for(int i=0;i<270;i++) { next[i]=NULL; } } }; trie root; int n=0; int m=1; void trie_add(char *c) { trie *p=&root; for(int i=0;i<strlen(c);i++) { int t; t=(int)c[i]; if((*p).next[t]==NULL) { (*p).next[t]=new trie; } p=(*p).next[t]; } if((*p).id==0) { (*p).id=m; for(int i=0;i<strlen(c);i++) { str[m][i]=c[i]; } m++; } num[(*p).id]++; } void ceshi() { for(int i=0;i<m;i++) { cout<<num[i]<<" "; } } void dfs(trie *p) { if((*p).id!=0) { printf("%s ",str[(*p).id]); double l; l=(double)num[(*p).id]/(double)n*100; printf("%.4lf\n",l); } for(int i=0;i<270;i++) { if((*p).next[i]==NULL)continue; dfs((*p).next[i]); } } int main() { char l[35]={0}; while(cin.getline(l,30)) { n++; trie_add(l); memset(l,0,sizeof(l)); } //ceshi(); //cout<<endl<<n<<endl; trie *p=&root; dfs(p); }
另外还有遍历过程中，输出字符串的问题，我是用一个另外的字符串数组在建立trie树的时候就存下了所有的id对应的字符串，其实应该是可以在遍历的时候，记录下各个节点表示的字符从而达到输出目的的，这样其实可以更省空间。
