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] = {{"

串的快速检索：

相关推荐