#include
<
iostream
>
#include
<
string
>
#include
<
vector
>
#include
<
algorithm
>
using
namespace
std;
typedef pair
<
int
,
int
>
word_index;
typedef pair
<
int
,
int
>
lv1_index;
#define
NOT_VALUE 0xffffffff
typedef
struct
dp_item {
int
min_word_amount;
int
min_word_seq[
200
];
//
最长的word序列也就是100个单字母组成
} dp_item;
string
words[
100010
];
dp_item dp[
200
]
=
{
0
};
//
号码最长是100个字符
lv1_index index_lv1[
100
];
//
一级索引使用数组，不用vector，因为这样可以更方便地根据 索引项的单词长度，随机访问一级索引，单个词最长也就50个字符
bool
cmp_index(
const
word_index
&
a,
const
word_index
&
b) {
if
( a.second
==
b.second )
return
a.first
<
b.first;
return
a.second
<
b.second;
}
char
letter_to_num(
char
letter) {
switch
(letter) {
case
'
i
'
:
case
'
j
'
:
return
'
1
'
;
case
'
a
'
:
case
'
b
'
:
case
'
c
'
:
return
'
2
'
;
case
'
d
'
:
case
'
e
'
:
case
'
f
'
:
return
'
3
'
;
case
'
g
'
:
case
'
h
'
:
return
'
4
'
;
case
'
k
'
:
case
'
l
'
:
return
'
5
'
;
case
'
m
'
:
case
'
n
'
:
return
'
6
'
;
case
'
p
'
:
case
'
r
'
:
case
'
s
'
:
return
'
7
'
;
case
'
t
'
:
case
'
u
'
:
case
'
v
'
:
return
'
8
'
;
case
'
w
'
:
case
'
x
'
:
case
'
y
'
:
return
'
9
'
;
case
'
o
'
:
case
'
q
'
:
case
'
z
'
:
return
'
0
'
;
}
}
bool
match(
const
string
&
sub_num,
const
string
&
word) {
for
(
int
i
=
0
; i
<
sub_num.length(); i
++
)
if
( letter_to_num(word[i])
!=
sub_num[i] )
return
false
;
return
true
;
}
int
main() {
string
number;
vector
<
word_index
>
sorted_index_lv2, sorted_index_lv1;
vector
<
word_index
>
::iterator it;
int
word_amount
=
0
, i, j, d, k, word_len, number_len, idx;
int
min, min_choice, min_choice_word;
cin
>>
number;
while
(number
!=
"
-1
"
) {
memset(dp, NOT_VALUE,
sizeof
(dp));
memset(index_lv1, NOT_VALUE,
sizeof
(index_lv1));
sorted_index_lv2.clear();
number_len
=
number.length();
cin
>>
word_amount;
if
( word_amount
==
0
||
number_len
==
0
) {
cout
<<
"
No solution.
"
<<
endl;
cin
>>
number;
continue
;
}
for
( i
=
0
;i
<
word_amount;i
++
)
cin
>>
words[i];
for
( i
=
0
;i
<
word_amount;i
++
)
sorted_index_lv2.push_back(make_pair(i, (
int
)(words[i].length())));
sort(sorted_index_lv2.begin(), sorted_index_lv2.end(), cmp_index);
//
完成二级索引
word_len
=
sorted_index_lv2[
0
].second;
index_lv1[word_len]
=
make_pair(
0
,
1
);
for
( i
=
1
; i
<
sorted_index_lv2.size(); i
++
) {
//
构造一级索引
if
( sorted_index_lv2[i].second
!=
word_len ) {
word_len
=
sorted_index_lv2[i].second;
//
长度为旧word_len的单词没有了，到新的word_len长度了
index_lv1[word_len]
=
make_pair(i,
1
);
//
记录第一个长度为word_len的单词在sorted_index_lv2中的位置i
}
else
{
index_lv1[word_len].second
++
;
//
找到多一个长度为word_len的单词
}
}
dp[
0
].min_word_amount
=
0
;
for
( i
=
1
;i
<=
number_len;i
++
) {
for
( k
=
0
, min_choice
=
-
1
; k
<
i; k
++
) {
if
( dp[k].min_word_amount
==
NOT_VALUE )
//
没有长k的匹配前缀，就算后面有长i-k的匹配后缀，也没用
continue
;
idx
=
index_lv1[i
-
k].first;
//
获取后缀长度的单词组的一级索引
if
( idx
==
NOT_VALUE )
//
没有长度为k的单词
continue
;
//
遍历所有长度为i的单词
for
( j
=
idx, d
=
0
; d
<
index_lv1[i
-
k].second; d
++
, j
++
) {
//
second保存的是，在二级索引中，有多少个索引项的单词是长度为i-k的。
if
( dp[i].min_word_amount
==
NOT_VALUE
||
dp[i].min_word_amount
>
dp[k].min_word_amount
+
1
) {
//
当k=0时，计算对象的就是后缀长度为i的单词
if
( match(number.substr(k, i
-
k), words[sorted_index_lv2[j].first]) ) {
//
判断长度为i-k的单词是否符合号码的相应部分
dp[i].min_word_amount
=
dp[k].min_word_amount
+
1
;
min_choice
=
k;
min_choice_word
=
sorted_index_lv2[j].first;
break
;
//
同一长度的单词，选第一个能匹配的就够
}
}
}
}
if
( dp[i].min_word_amount
!=
NOT_VALUE ) {
//
长度为i的前缀串拥有最短匹配单词组
if
( dp[min_choice].min_word_amount
>
0
)
memcpy(dp[i].min_word_seq, dp[min_choice].min_word_seq,
sizeof
(
int
)
*
dp[min_choice].min_word_amount);
//
不用担心最初序列长度是0，因为什么都不复制 ^_^
dp[i].min_word_seq[ dp[i].min_word_amount
-
1
]
=
min_choice_word;
}
}
if
( dp[number_len].min_word_amount
==
NOT_VALUE ) {
cout
<<
"
No solution.
"
<<
endl;
}
else
{
for
( i
=
0
; i
<
dp[number_len].min_word_amount
-
1
; i
++
)
cout
<<
words[ dp[number_len].min_word_seq[i] ]
<<
"
"
;
cout
<<
words[ dp[number_len].min_word_seq[i] ]
<<
endl;
}
cin
>>
number;
}
return
0
;
}
情结的一题，从大一开始就一直想AC，但一直做到大一尾声也做不出来，相隔3年了，昨晚就随便15分钟想出了算法。
DP的情况是比较简单的，只是如何操纵字符串有点难度，通过建立2级的索引，可以用过长度来索引到所有拥有该长度的单词，最后就剩下个DP的过程。
