智能T9英文输入法
Time Limit:1000MSMemory Limit:30000KB
Total Submit:235Accepted:57
Description
某款新型手机为了方便用户,希望开发一种新的英文输入法.要求在输入英文的时候输入法不但能够做到自动联想,还能进行自动
纠错.譬如用户希望输入hello这个单词,他应该输入43556,但是他不小心输入了46556.输入法发现词库中找不到任何匹配的单词,
于是尝试把6纠正为3,这便是纠错功能.现在需要你来开发这个输入法的核心部分.
给出词库和用户的输入,请你依次给出适合的单词.
2 A B C
3 D E F
4 G H I
5 J K L
6 M N O
7 P Q R S
8 T U V
9 W X Y Z
注意：1和0没有对应的字母,但是1和0也有可能出现.
Input
该题含有多组测试数据。
每组数据第一行是一个整数n(1<=n<=100),表示词库中的单词个数.
接下来n行每行是一个词库中的单词.单词只包含大写字母,长度不会超过10.不会出现两个相同的单词.
最后一行是一个数字串表示用户的输入.输入的长度不会超过10.
Output
对于每组测试数据的输出,包含四个部分.
首先输出完全符合输入的单词.
然后是根据联想得到的单词,即前缀部分完全符合输入的单词.
接下来输出纠正一个按键之后完全符合输入的单词.
然后是纠正一个按键之后联想得到的单词.
每部分如果有多个匹配，则按字典顺序输出.
保证不会出现无解情况.
Sample Input
6
BVUJMEE
MUTKOE
BTVLOE
ATVKEI
EVTJNJHF
OVVLMFAABC
288563
Sample Output
BTVLOE
BVUJMEE
MUTKOE
OVVLMFAABC
Source
浙江省2004组队赛第二试(From TOJ)
暴力，深度优先搜索，根据输入数字，穷举所有可能的字母组合，判断每种字母组合是否符合要求。
睡觉前心血来潮想写写这个题目，结果写到现在，明天补觉。
1
#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5#define N 109
6#define L 13
7#define K 13
8#define E ('Z'+1)
9#define P 13
10
11int n;
12char word[ N ][ L ];
13char key[ K ] = "**ADGJMPTW*";
14
15int m;
16char press[ P ];
17
18
/**//* 二维字符数组 */
19int cmpA( const void *a, const void *b ) 
{
20
return strcmp( ((const char*)a), ((const char*)b) );
21
}
22 /**//* 一维字符指针 */
23int cmpP( const void *a, const void *b ) {
24 return strcmp( (*((const char**)a)), (*((const char**)b)) );
25}
26
27int topAns, topPre, topAns1, topPre1;
28char *ans[ N ], *pre[ N ], *ans1[ N ], *pre1[ N ];
29
30char tmp[ P ];
31int mod1;
32
33void update() {
34 int i, j;
35
for ( i = 0; i < n; ++i ) {
36 for ( j = 0; (tmp[j])&&(word[i][j])&&(tmp[j]==word[i][j]); ++j )
37 ;
38 if ( 0 == tmp[ j ] ) {
39 if ( 0 == word[ i ][ j ] ) {
40 if ( mod1 ) {
41 ans1[ topAns1++ ] = word[ i ];
42
}
43 else {
44 ans[ topAns++ ] = word[ i ];
45 }
46 }
47 else {
48 if ( mod1 ) {
49 pre1[ topPre1++ ] = word[ i ];
50 }
51 else {
52 pre[ topPre++ ] = word[ i ];
53 }
54 }
55 }
56 }
57}
58
59void solve( int i ) {
60 char j, k;
61 if ( i >= m ) {
62 tmp[ i ] = 0;
63 update();
64 return;
65 }
66 for ( j = key[ press[ i ] ]; j < key[ press[ i ] + 1 ]; ++j ) {
67 tmp[ i ] = j;
68 solve( i+1 );
69 }
70 if ( 0 == mod1 ) {
71 mod1 = 1;
72 for ( k = 2; k < 10; ++k ) {
73 if ( k == press[ i ] ) {
74 continue;
75 }
76 for ( j = key[ k ]; j < key[ k + 1 ]; ++j ) {
77 tmp[ i ] = j;
78 solve( i+1 );
79 }
80 }
81 mod1 = 0;
82 }
83}
84
85void out( int top, char * stack[] ) {
86 int i;
87 if ( top > 0 ) {
88 qsort( stack, top, sizeof(char*), cmpP );
89 for ( i = 0; i < top; ++i ) {
90 puts( stack[ i ] );
91 }
92 }
93}
94
95void output() {
96 out( topAns, ans );
97 out( topPre, pre );
98 out( topAns1, ans1 );
99 out( topPre1, pre1 );
100}
101
102int main() {
103 int i;
104 key[ 0 ] = key[ 1 ] = key[ 10 ] = E;
105 while ( 1 == scanf( "%d", &n ) ) {
106 for ( i = 0; i < n; ++i ) {
107 scanf( "%s", word[ i ] );
108 }
109 /**//* qsort( word, n, sizeof(word[0]), cmpA ); */
110 scanf( "%s", press );
111 m = strlen( press );
112 for ( i = 0; i < m; ++i ) {
113 press[ i ] -= '0';
114 }
115 topAns = topPre = topAns1 = topPre1 = 0;
116 mod1 = 0;
117 solve( 0 );
118 output();
119 }
120 return 0;
121}
122
09年10月通过的代码，用了 Trie ，懒得分析了。
1#include <iostream>
2#include <cstring>
3using namespace std;
4
5char * letter[300];
6
7#define TW ('Z'+1)
8#define TWB 'A'
9#define EOW 0
10struct WordNode
11{
12 WordNode(){
13 bExist = 0;
14 memset( ch, 0, sizeof(ch) );
15 }
16 int bExist;
17 WordNode * ch[TW];
18};
19
20WordNode * root = 0;
21
22#define WL 20
23#define NW 100000
24char fw[NW][WL], wz[WL];
25int nw, nz;
26
27void WordInsert( WordNode * & roo, char * p ){
28 if( roo == 0 ){
29 roo = new WordNode;
30 }
31 if( *p != EOW ){
32 WordInsert( roo->ch[*p], p+1 );
33 }
34 else{
35 roo->bExist = 1;
36 }
37 return;
38}
39
40void WordClear( WordNode * & roo ){
41 char i;
42 if( roo == 0 ){
43 return;
44 }
45 for( i=TWB; i<TW; ++i ){
46 WordClear( roo->ch[i] );
47 }
48 delete roo;
49 roo = 0;
50 return;
51}
52
53void FindWord( WordNode * roo, char * p ){
54 char *pl;
55 if( roo == 0 ){
56 return;
57 }
58 if( *p == EOW ){
59 if( roo->bExist ){
60 strcpy( fw[nw], wz );
61 ++nw;
62 }
63 return;
64 }
65 if( (*p=='0') || (*p=='1') ){
66 return;
67 }
68
69 ++nz;
70 for( pl=letter[*p]; *pl!=EOW; ++pl ){
71 wz[nz-1] = *pl;
72 FindWord( roo->ch[*pl], p+1 );
73 }
74 wz[--nz] = 0;
75 return;
76}
77
78void FindAssociateWord( WordNode * roo, char * p ){
79 char *pl, i;
80 if( roo == 0 ){
81 return;
82 }
83
84 if( p == 0 ){
85 if( roo->bExist ){
86 strcpy( fw[nw], wz );
87 ++nw;
88 }
89 ++nz;
90 for( i=TWB; i<TW; ++i ){
91 wz[nz-1] = i;
92 FindAssociateWord( roo->ch[i], 0 );
93 }
94 wz[--nz] = 0;
95 return;
96 }
97
98 if( *p == EOW ){
99 ++nz;
100 for( i=TWB; i<TW; ++i ){
101 wz[nz-1] = i;
102 FindAssociateWord( roo->ch[i], 0 );
103 }
104 wz[--nz] = 0;
105 return;
106 }
107
108 if( (*p=='0') || (*p=='1') ){
109 return;
110 }
111
112 ++nz;
113 for( pl=letter[*p]; *pl!=EOW; ++pl ){
114 wz[nz-1] = *pl;
115 FindAssociateWord( roo->ch[*pl], p+1 );
116 }
117 wz[--nz] = 0;
118 return;
119}
120
121void FindOutput( void ){
122 char * w[NW], *temp;
123 int i, j, k;
124 for( i=0; i<nw; ++i ){
125 w[i] = fw[i];
126 }
127 for( i=0; i<nw; ++i ){
128 k = i;
129 for( j=i+1; j<nw; ++j ){
130 if( strcmp( w[k], w[j] ) > 0 ){
131 k = j;
132 }
133 }
134 if( k != i ){
135 temp = w[k]; w[k] = w[i]; w[i] = temp;
136 }
137 printf( "%s\n", w[i] );
138 }
139 nw = 0;
140 return;
141}
142
143int main(){
144 int n;
145 char tc, s[WL], *pc, i;
146
147 memset( letter, 0, sizeof(letter) );
148 letter['2'] = "ABC";
149 letter['3'] = "DEF";
150 letter['4'] = "GHI";
151 letter['5'] = "JKL";
152 letter['6'] = "MNO";
153 letter['7'] = "PQRS";
154 letter['8'] = "TUV";
155 letter['9'] = "WXYZ";
156
157 while( EOF != scanf( "%d", &n ) ){
158 WordClear( root );
159
160 while( n-- ){
161 scanf( "%s", s );
162 WordInsert( root, s );
163 }
164 scanf( "%s", s );
165
166 nw = nz = 0;
167 FindWord( root, s );
168 FindOutput();
169
170 nw = nz = 0;
171 FindAssociateWord( root, s );
172 FindOutput();
173
174 nw = nz = 0;
175 for( pc=s; *pc!=EOW; ++pc ){
176 for( i='2'; i<='9'; ++i ){
177 if( i != *pc ){
178 tc = *pc;
179 *pc = i;
180 FindWord( root, s );
181 *pc = tc;
182 }
183 }
184 }
185 FindOutput();
186
187 nw = nz = 0;
188 for( pc=s; *pc!=EOW; ++pc ){
189 for( i='2'; i<='9'; ++i ){
190 if( i != *pc ){
191 tc = *pc;
192 *pc = i;
193 FindAssociateWord( root, s );
194 *pc = tc;
195 }
196 }
197 }
198 FindOutput();
199 }
200 return 0;
201}
202