|
题目大意：有很多单词而且是按照字典序排列的，现在要你找到有哪些单词由两个单词连接而成。
思路：把所有单词放到set中，判断是否可以由其它两个单词组成。substr函数可以分割单词。小优化：既然是按字典序排列的，那么这个单词和上个单词前多少个字母相同的数量就是这个单词所能分割的最大长度。比如 never neverless oop 那第二个单次所能分割的最大只有5个，opp则不能分割。
#include<string>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
int strcc(string s1,string s2){
int i=0;
int len=min(s1.length(),s2.length());
for(;i<s1.length();){
if(s1[i]==s2[i]) i++;
else return i;
}
}
int main()
{
set<string> s;
string s1;
while(cin>>s1) s.insert(s1);
set<string>::iterator i,j;
for(i=j=s.begin(),j++;j!=s.end();i++,j++){
string s3=*i;
string s2=*j;
//cout<<s3<<" "<<s2<<endl;
int len=strcc(s2,s3);
for(int k=1;k<=len;k++){
if(s.find(s2.substr(0,k))!=s.end()&&s.find(s2.substr(k,s2.length()-k))!=s.end()){
cout<<s2<<endl;
break;
}
}
}
return 0;
}
| 
转播
