|
题目描述：给出一个词典，找出所有的复合词，即恰好有两个单词连接而成的单词。输入每行都是一个由小写字母组成的单词。输入已按照字典序从小到大排序，且不超过12000个单词。输出所有的复合词按照字典序从小到大排列。
思路：用set存储所有的单词，对于每个单词，遍历所有可能子单词组合，然后判断在set中是否都已经存储，若是则输出该单词。算法复杂度为O(n*lgn*|S|)，其中|S|表示单词最大长度。
代码如下：
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <sstream>
#include <fstream>
using namespace std;
#define FILE
int main()
{
#ifdef FILE
ifstream in("data.txt");
ofstream out("output.txt");
cin.rdbuf(in.rdbuf());
cout.rdbuf(out.rdbuf());
#endif
set<string> res;
string str;
while(cin>>str)
{
res.insert(str);
}
for(set<string>::iterator it=res.begin();it!=res.end();it++)
{
string a = *it;
int n = a.size();
for(int i=0;i<a.size();i++)
{
string pre = a.substr(0,i+1);
string next = a.substr(i+1,n-i);
if(res.find(pre)!=res.end()&&res.find(next)!=res.end())
{
cout<<a<<endl;
break;
}
}
}
return 0;
}
| 
转播
