POJ 1451 -- T9

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 4131		Accepted: 1481

Sample Input

2
5
hell 3
hello 4
idea 8
next 8
super 3
2
435561
43321
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771

Sample Output

Scenario #1:
i
id
hel
hell
hello

i
id
ide
idea


Scenario #2:
p
pr
pro
prog
progr
progra
program

n
ne
new

g
in
int

c
co
con
cont
anoth
anothe
another

p
pr
MANUALLY
MANUALLY

题意：

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

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

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

思路：

字典树的应用，使用字典树对单词进行统计

使用深度搜索遍历字典树，进行词义猜测

Tips：

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

※ 【网上摘录】

串的快速检索：

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

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

串的排序：

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

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

最长公共前缀问题：

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

  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 using namespace std;
  5 const int maxl = 110;
  6 char word[10][5] = {{""},
  7                 {""},{"abc"},{"def"},
  8                 {"ghi"},{"jkl"},{"mno"},
  9                 {"pqrs"},{"tuv"},{"wxyz"}};
 10 
 11 char In[maxl];///接受输入字符串，建立字典树
 12 char inNum[maxl];///接受输入的数字按键
 13 char ans[maxl];///输出数组
 14 char tmp[maxl];///输出数组的临时数组，比较概率大小
 15 int pro;
 16 
 17 class HashTable{
 18 public:
 19     HashTable *next[26];
 20     int Count;//概率
 21     HashTable()//初始化
 22     {
 23         Count = 0;
 24         memset(next,0,sizeof(next));
 25     }
 26 }*root;//根节点
 27 
 28 
 29 void Insert(int num)
 30 {
 31     int i = 0;
 32     HashTable *temp = root;
 33     while(In[i])
 34     {
 35         if(!temp->next[In[i]-'a'])///为空
 36         {
 37             temp->next[In[i]-'a'] = new HashTable;
 38         }
 39         temp = temp->next[In[i]-'a'];
 40         temp->Count += num;
 41         i++;
 42     }
 43 }
 44 
 45 void find(int End,int pos,HashTable *r)
 46 {
 47     int len = strlen(word[inNum[pos]-'0']);
 48     HashTable *temp = r;
 49     for(int i=0;i<len;i++)
 50     {
 51        int pi = word[inNum[pos]-'0'][i] - 'a';
 52        if(!temp->next[pi]) continue;
 53        tmp[pos] = word[inNum[pos]-'0'][i];
 54        if(pos == End)//检索结束
 55        {
 56            if(temp->next[pi]->Count > pro)
 57             {
 58                 strcpy(ans,tmp);
 59                 pro = temp->next[pi]->Count;
 60             }
 61        }
 62        else
 63         find(End,pos+1,temp->next[pi]);
 64     }
 65 }
 66 
 67 int main()
 68 {
 69     int turn;
 70     int turnCount = 1;
 71     while(cin>>turn)
 72     {
 73         while(turn--)
 74         {
 75             root = new HashTable;
 76             ///输入字符串和频数
 77             int a;
 78             cin>>a;
 79             for(int i=1;i<=a;i++)
 80             {
 81                 int num;
 82                 cin>>In>>num;
 83                 ///将读入的字符插入字典
 84                 Insert(num);
 85             }
 86 
 87             cout<<"Scenario #"<<turnCount++<<":"<<endl;
 88 
 89             ///输入按键
 90             cin>>a;
 91             while(a--)
 92             {
 93                 cin>>inNum;
 94                 ///将读入的按键进行处理
 95                 int len = strlen(inNum);
 96                 for(int i=0;i<len-1;i++)///注意末尾是1
 97                 {
 98                     pro = 0;
 99                     memset(tmp,0,sizeof(tmp));
100                     find(i,0,root);
101                     if(pro == 0)//没有找到
102                         cout<<"MANUALLY"<<endl;
103                     else{
104                         cout<<ans<<endl;
105                     }
106                 }
107                 cout<<endl;
108             }
109             cout<<endl;
110             delete root;
111         }
112     }
113     return 0;
114 }