原題貼上
?
?
10391 Compound Words
?
You are to find all the two-word compound words in a dictionary. A two-word compound word is a
word in the dictionary that is the concatenation of exactly two other words in the dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will
be no more than 120,000 words.
Output
Your output should contain all the compound words, one per line, in alphabetical order.
Sample Input
a
alien
born
less
lien
never
nevertheless
new
newborn
the
zebra
Sample Output
alien
newborn
?
?
?
分析：最好的方法是用hash算法，可是我暫時還不會這種算法。還好可以用map存儲字典再查找，
然而這里有2中查找方式???一、以輸入單詞作為查找對象?，這就需要將所有輸入的單詞2—2組合存為一個字典，再遍歷輸入的單詞看是否能找到，這里的輸入數(shù)據(jù)會很大，可能達到120000，這種查找方式的復雜度o(n^2),如果這樣做會TLE
方式二?、已輸入單詞的部分作為對象，這樣就不用將單詞2-2組合，而只需要將一個單詞拆分，一個單詞最多也就40個字母吧，那么遍歷左右拆分后的單詞的復雜度只有?o（n*40）????也就是o（n）,這樣就不會TLE了
?
?
下面貼上方式二?的代碼
#include <iostream>
#include
<cstdlib>
#include
<cstdio>
#include
<cstring>
#include
<map>
using
namespace
std;
map
<
string
,
int
>
Map;
int
n;
char
str[
120010
][
30
];
int
main()
{
Map.clear();
n
=
0
;
while
(~scanf(
"
%s
"
, str[n])){
Map[str[n]]
=
1
;
n
++
;
}
for
(
int
i =
0
; i < n; i++
)
{
int
len =
strlen(str[i]);
for
(
int
j =
1
; j < len; j++
)
{
char
temp1[
30
] = {
'
\0
'
};
char
temp2[
30
] = {
'
\0
'
};
strncpy(temp1, str[i], j);
strncpy(temp2, str[i]
+ j, len -
j);
if
(Map[temp1] &&
Map[temp2])
{
printf(
"
%s\n
"
, str[i]);
break
;
}
}
}
return
0
;
}
?
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
