Compound Words(复合词) UVA 10391

解题思路：这道题开始考虑通过合成单词来做，结果超时（复杂度n*n）；后面考虑通过分解单词来做(复杂度n*m(m表示单词平均长度))AC了，需要用到string中的分解函数substr(可以在STL中查询)

#include<iostream>
#include<string>
#include<vector>
#include<set>
using namespace std;
vector<string>vec; //通过下标遍历输入的单词
set<string>set1; //用于保存输入的单词
set<string>set2; //用于保存输出的单词
int main(){
string str;
while(cin>>str){
set1.insert(str);
vec.push_back(str);
}
for(int i=0;i<vec.size();i++){
string s1,s2;
if(vec[i].size()>1){
for(int j=0;j<vec[i].size()-1;j++){
s1=vec[i].substr(0,j+1);
s2=vec[i].substr(j+1);
if(set1.count(s1) && set1.count(s2))set2.insert(vec[i]); //当分解成两份后的单词满足条件时,插入到输出集合中
}
}
}
for(set<string>::iterator iter=set2.begin();iter!=set2.end();iter++){
cout<<*iter<<endl;
}
return 0;
}