紫书第五章训练2 F - Compound Words-蒲公英云

紫书第五章训练2 F - Compound Words

悠悠 2021-12-16 12:49 330阅读 0赞

F - 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

这个题就是找个单词是已出现两个单词的和，我用map写一直错，我分析了下大概是每次都要访问map，然后map的空间就不够了，所以还是用set搞下不错，他和map的查询复杂度都是logn的，运用string还有find岂不是很简单实用，美滋滋

不过需要提出的是字典树或者直接数组搞会比stl速度快些的

#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
set<string>ma;
while(cin>>s){
    ma.insert(s);
}
set<string>::iterator it;
for(it=ma.begin();it!=ma.end();it++){
    string c=*it;
    for(int i=1;c[i];i++){
        if(ma.find(c.substr(0,i))!=ma.end()&&ma.find(c.substr(i))!=ma.end()){
            cout<<c<<endl;
            break;
        }
    }
}
return 0;}