一、题目
输入一系列由小写字母组成的单词。输入已按照字典序排序（这句话就是个陷阱），且不超过120000个。找出所有的复合词，即恰好由两个单词连接而成的单词。
二、解题思路
要么枚举两两拼接的情况，O(n^2),n这么大肯定会超时。要么枚举每个单词的拆分情况，当单词比较短时，O(n*m),可能可行。
我们用string类型的数组存储这些单词，map记录单词的是否出现，set自动排序并去重。
三、代码
#include<stdio.h>
#include<iostream>
#include<stdbool.h>
#include<string>
#include<set>
#include<map>
#include<algorithm>
using namespace std; const int maxn = + ;
string words[maxn];
map<string, bool>myhash;
set<string>ans; int main()
{
int cnt = ;
while (cin >> words[cnt])
{
myhash[words[cnt++]] = true;
}
for (int i = ; i < cnt; i++)
{
for (int j = ; j < words[i].size() - ; j++)
{
string a = words[i].substr(, j + );
string b = words[i].substr(j + );
if (myhash[a] && myhash[b])
{
ans.insert(words[i]); //这里直接输出好像不对，可能出现重复的情况
}
}
}
for (set<string>::iterator it = ans.begin(); it != ans.end(); it++)
cout << *it;
return ;
}