poj2418Hardwood Species
9030 ワード
http://poj.org/problem?id=2418
trieツリー、スペース、アルファベット以外の文字
View Code
trieツリー、スペース、アルファベット以外の文字
View Code
1 #include <iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<stdlib.h>
5 #include<algorithm>
6 using namespace std;
7 typedef struct node
8 {
9 int num;
10 struct node *next[130];
11 node()
12 {
13 memset(next,NULL,sizeof(next));
14 num = 0;
15 }
16 }trie;
17 int y,k;
18 char ss[10010][40],w[40];
19 void ctrie(trie *t,char *x)
20 {
21 int i,j,d,k = strlen(x);
22 char yy[40];
23 strcpy(yy,x);
24 trie *p = t;
25 for(i = 0 ; i < k ; i++)
26 {
27 d = x[i];
28 if(p->next[d]==NULL)
29 {
30 p->next[d] = new node;
31 }
32 p = p->next[d];
33 }
34 if(p->num==0)
35 {
36 strcpy(ss[y],yy);
37 y++;
38 }
39 p->num++;
40 }
41 void dfs(trie *t,int x)
42 {
43 trie *p = t;
44 int i;
45 if(p->num>0)
46 {
47 w[x] = '\0';
48 printf("%s %.4lf
",w,p->num*100.0/k);
49 }
50 for(i = 1; i <= 129 ; i++)
51 {
52 if(p->next[i]!=NULL)
53 {
54 w[x] = i;
55 dfs(p->next[i],x+1);
56 }
57 }
58 }
59 int main()
60 {
61 int i,j;
62 char s[40];
63 trie *t = new node;
64 while(gets(s)!=NULL)
65 {
66 k++;
67 ctrie(t,s);
68 }
69 dfs(t,0);
70 return 0;
71 }