原题贴上
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组合存为一个字典，再遍历输入的单词看是否能找到，这里的输入数据会很大，可能达到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
;
}
