UVA 10391 Compound Words-白红宇

UVA 10391 Compound Words

阅读量：6320 次

发布时间：2019-06-22

本文共 934 字，大约阅读时间需要 3 分钟。

思路：

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

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

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

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
            8 #define maxn 120005 9 using namespace std;10 string word[maxn];11 map
            
              dic;12 set
             
               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
              
               ::iterator it = res.begin(); it != res.end(); it++)38 cout << *it << endl;39 40 return 0;41 }