UVA 10391 Compound Words-蒲公英云

UVA 10391 Compound Words

思路：

　　遍历拼接会超限，但是可以往下拆解；用一个map存一个单词是否是输入的(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 }