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

悠悠 2021-12-16 12:49 230阅读 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 条评论，230人围观）

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

相关阅读

相关《以书为友第五章》

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

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

相关 Compound Words(复合词) UVA 10391

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

﹏ヽ暗。殇╰゛Y/ 2024年02月17日 18:48/ 0 赞/ 23 阅读

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

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

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

相关紫书的训练计划——一点点来，坚持到底！

![Image 1][] ![Center][] 先做第10章3 数论的一点补充。然后趁热温习 10.1 和10.2 （可能

旧城等待，/ 2022年08月09日 12:55/ 0 赞/ 17 阅读

相关 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 赞/ 103 阅读

相关 UVA 10391 Compound Words

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

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

相关紫书第五章训练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 赞/ 231 阅读

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

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

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

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

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

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

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

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

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