UVA 10391 Compound Words

àì夳堔傛蜴生んèń 2022-01-06 11:45 124阅读 0赞

思路：

遍历拼接会超限，但是可以往下拆解；用一个map<string,bool>存一个单词是否是输入的(true)，

遍历拆解单词，寻找它拆分出的两个词s1，s2有没有在map里面值为true；如果是，就装到

set里面（因为题目要求字典序输出），最后输出结果。

1 #include<iostream>
     2 #include<cstdio>
     3 #include<string>
     4 #include<cstring>
     5 #include<set>
     6 #include<vector>
     7 #include<map>
     8 #define maxn 120005
     9 using namespace std;
    10 string word[maxn];
    11 map<string, bool> dic;
    12 set<string> res;
    13 int main()
    14 {
    15     string str;
    16     int cnt = 0;
    17     while (getline(cin, str))
    18     {
    19         dic[str] = true;
    20         word[cnt++] = str;
    21     }
    22 
    23     for (int i = 0; i < cnt; i++)
    24     {
    25         for (int j = 0; j < word[i].length(); j++)
    26         {
    27             string s1 = word[i].substr(0, j);
    28             string s2 = word[i].substr(j);
    29             if (dic[s1] && dic[s2])
    30             {
    31                 
    32                 res.insert(word[i]);
    33             }
    34         }
    35     }
    36 
    37     for (set<string>::iterator it = res.begin(); it != res.end(); it++)
    38         cout << *it << endl;
    39     
    40     return 0;
    41 }

转载于:https://www.cnblogs.com/fudanxi/p/10382305.html

发表评论取消回复

表情：

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

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

相关阅读

相关 Play on Words 单词 UVA 10129 (欧拉+dfs)

概念：无向图中欧拉道路（也叫欧拉通路），需要满足的条件图是连通的并且最多只有两个奇顶点（这两个奇顶点是欧拉通路的端点）；欧拉回路：图是连通的并且没有奇顶点。有向图中也相

淩亂°似流年/ 2024年02月17日 18:56/ 0 赞/ 36 阅读

相关 Compound Words(复合词) UVA 10391

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

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

相关 UVA642 Word Amalgamation(查字典类)

经典的查字典题+经典的map应用题目描述在美国各地的数百万份报纸中，有一款名为Jumble的文字游戏。这个游戏是要解决一个谜语，但为了找到答案中出现的字母来解读四

Love The Way You Lie/ 2023年06月13日 14:28/ 0 赞/ 25 阅读

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

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

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

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

相关 UVA - 10924 - Prime Words (素数)

输入一个由大小写字母组成的字符串，每个字符代表着不同的数字，计算出这个字符串的数值，判断是否是素数；首先我们打个素数表；然后利用ascll码存入数组中，然后判断就o

r囧r小猫/ 2022年06月07日 00:23/ 0 赞/ 168 阅读

相关递推/DP(动态规划)UVA 10081-Tight Words

递推/DP(动态规划)UVA 10081-Tight Words -------------------- 题目链接：[10081 - Tight Wor

矫情吗；*/ 2022年05月16日 09:12/ 0 赞/ 206 阅读

相关 Play on Words UVA - 10129 (欧拉路径)

Some of the secret doors contain a very interesting word puzzle. The team of archaeologi

绝地灬酷狼/ 2022年02月26日 03:14/ 0 赞/ 166 阅读

相关 UVA 10391 Compound Words

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

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

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