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

悠悠 2021-12-16 12:49 186阅读 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速度快些的

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#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;}

转载于:https://www.cnblogs.com/BobHuang/p/6842868.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/e1fb97f592094da88dd2222b93ed2024.png

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关《以书为友第五章》

带着上一个领域的知识积木进入下一个、再下一个领域时，这些知识汇聚到一起，形成了一个可怕的复杂系统——大师思想从中诞生。不能解决当下问题的，降低关注度。并不是否认这个知识好...

骑猪看日落/ 2024年04月29日 01:16/ 0 赞/ 20 阅读

相关复合词 (Compound Words)(集合+字符函数)

题目描述给出一个词典，找出所有的复合词，即恰好有两个单词连接而成的单词。输入每行都是一个小写字母组成的单词。输入已按照字典序从小到大排序，且不超过120000个单词。输

╰+攻爆jí腚メ/ 2022年11月30日 04:26/ 0 赞/ 161 阅读

相关西瓜书学习记录-神经网络（第五章）

西瓜书学习记录-神经网络（第五章）第五章啦，大佬的视频没讲第五章，所以看书自学一下： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5

亦凉/ 2022年10月25日 12:49/ 0 赞/ 143 阅读

相关 css3基础知识第五章实战训练

只需要css就可以达到的效果：导航栏，图片选中透明效果，背景透明效果，自定义文字选中颜色导航栏水平菜单只需在纵向菜单的基础上去掉ul的宽度；li加浮动；然后改一

淩亂°似流年/ 2022年08月10日 06:20/ 0 赞/ 173 阅读

相关 UVA 10391 Compound Words

You are to find all the two-word compound words in a dictionary. A two-word compound wor

比眉伴天荒/ 2022年06月07日 02:21/ 0 赞/ 58 阅读

相关 UVA 10391 Compound Words

思路：　　遍历拼接会超限，但是可以往下拆解；用一个map<string,bool>存一个单词是否是输入的(true)，　　遍历拆解单词，寻找它拆分出的两个词s1，s2有

àì夳堔傛蜴生んèń/ 2022年01月06日 11:45/ 0 赞/ 88 阅读

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

F - Compound Words You are to find all the two-word compound words in a dictionary. A

悠悠/ 2021年12月16日 12:49/ 0 赞/ 187 阅读

相关（紫书，感谢作者）第7章暴力求解法

今天，我们谈一谈紫书上面的内容——暴力求解法对于一道问题来说，我们是可以借助计算机运算快的特点，将所有可能的情况全部（不一定是全部）列出来，然后去寻找我们想要的答案

今天药忘吃喽~/ 2021年12月09日 07:51/ 0 赞/ 212 阅读

相关 C++primerplus书摘2（第五到第八章）

1.字符函数 1 include<iostream> 2 include<cstdio> 3 include<cstring> 4 in

短命女/ 2021年11月17日 17:40/ 0 赞/ 211 阅读

相关编译原理（紫龙书）第2版习题答案

转载于某大佬的github用来收藏[https://github.com/fool2fish/dragon-book-exercise-answers/find/master]

刺骨的言语ヽ痛彻心扉/ 2021年07月16日 22:38/ 0 赞/ 597 阅读