#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的過程。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
