POJ 1451 T9 <Trie> 找出现频率最高的字符串

题意：

现实生活问题：用手机打字

先给出n个单词表示常用单词

然后用户按手机键盘上面的数字键.要求用户每按一个数字键，手机弹出可能性最大的单词

思路：

基础的Trie应用..

用字典序构造手机词典..

并累计每一个单词前缀串出现的概率.

然后创建数字和字母的映射表(1-3)..

计算所有可能前缀串的概率值..

Tips：

※ 字典树的典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

※ 【网上摘录】

串的快速检索：

　　给出N个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。

　　在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。

串的排序：

　　给定N个互不相同的仅由一个单词构成的英文名，让你将他们按字典序从小到大输出

　　用字典树进行排序，采用数组的方式创建字典树，这棵树的每个结点的所有儿子很显然地按照其字母大小排序。对这棵树进行先序遍历即可。

最长公共前缀问题：

　　对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为最近公共祖先问题。

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #define clr(x) memset(x, 0, sizeof(x))
 4 
 5 struct Tree
 6 {
 7     int count;
 8     Tree *next[26];
 9     Tree()
10     {
11         count = 0;
12         for(int i = 0; i < 26; ++i)
13             next[i] = NULL;
14     }
15 };
16 
17 char que[110], arr[110];
18 char tmp[110], ans[110];
19 int pro;
20 
21 char op[10][5] = {{"\0"}, {"\0"}, {"abc"}, {"def"}, {"ghi"}, {"jkl"}, {"mno"}, {"pqrs"}, {"tuv"}, {"wxyz"}};
22 
23 void add(char *s, int num, Tree *root)
24 {
25     int i = 0, x;
26     Tree *p = root;
27     while(s[i])
28     {
29         x = s[i]-'a';
30         if(p->next[x] == NULL)
31             p->next[x] = new Tree();
32         p = p->next[x];
33         p->count += num;
34         ++i;
35     }
36 }
37 
38 void find(int x, int pos, Tree *root)
39 {
40     Tree *p = root;
41     int tmpos = que[pos]-'0';
42     int len = strlen(op[tmpos]);
43 
44     for(int i = 0; i < len; ++i){
45         int tmpx = op[tmpos][i]-'a';
46         if(p->next[tmpx] == NULL) continue;
47         else tmp[pos] = op[tmpos][i];
48         if(pos == x){
49             if(p->next[tmpx]->count > pro){
50                 pro = p->next[tmpx]->count;
51                 strcpy(ans, tmp);
52             }
53         }
54         else find(x, pos+1, p->next[tmpx]);
55     }
56 }
57 
58 int main()
59 {
60     Tree *root;
61     int T, n, sum;
62     int k = 1;
63     freopen("e:\\acm\\mess\\stdin-stdout\\1451.txt", "r", stdin);
64     while(scanf("%d", &T) != EOF)
65     while(T--)
66     {
67         root = new Tree();///!!build a new tree
68 
69         printf("Scenario #%d:\n", k++);
70 
71         scanf("%d", &n);
72         while(n--){
73             scanf("%s %d", arr, &sum);
74             add(arr, sum, root);
75         }
76 
77         scanf("%d", &n);
78         while(n--){
79             scanf("%s", que);
80             int len = strlen(que);
81             for(int i = 0; i < len-1; ++i){///!!pay attention that it has a 1
82                 pro = 0;
83                 clr(tmp);
84                 find(i, 0, root);
85 //printf("---------------->>>\n");
86                 if(pro == 0) puts("MANUALLY");
87                 else printf("%s\n", ans);
88             }
89             puts("");
90         }
91         puts("");
92         delete root;
93     }
94     return 0;
95 }