算法竞赛入门经典第二版习题5-5 复合词 Compound Words uva10391

本文主要是介绍算法竞赛入门经典第二版习题5-5 复合词 Compound Words uva10391，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：https://vjudge.net/problem/UVA-10391

思路：用vector存下单词，因为单词已按字典序排列于是复合词前半个单词一定在这个复合词之前，于是遍历寻找在首字母更变之前是否有单词的前半部分和当前单词相同，然后再在整个vector中寻找是否有后半个部分的单词，若有，即是答案，用set存下来。一是set的有序性可以让答案按字典序排列，二是可以去重。最后输出即可。
注：题干有个错——A two-word compound word is a
word in the dictionary that is the concatenation of exactly two other words in the dictionary.
这句话有毒，明明说了要用两不同单词合成结果加判断条件就Wrong Answer……

代码：

#include <iostream>
#include <string>
#include <cstdio>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;set<string> ans;
vector<string> data;bool issame(const string &part, const string &whole)
{if(whole.size()<=part.size()){return false;}for(int i=0; i<part.size(); i++){if(part[i]!=whole[i]){return false;}}return true;
}int main()
{string s;while(cin >> s){data.push_back(s);}for(int i=0; i<data.size()-1; i++){if(data[i].empty()){continue;}for(int j=i+1; j<data.size(); j++){if(data[j].empty()){continue;}if(data[i][0]!=data[j][0]){break;}if(issame(data[i], data[j])){string t;for(int k=data[i].size(); k<data[j].size(); k++){t.push_back(data[j][k]);}vector<string>::iterator iter = find(data.begin(), data.end(), t);if(iter!=data.end()){ans.insert(data[j]);}}}}for(set<string>::iterator it = ans.begin(); it!=ans.end(); ++it){cout << *it << endl;}return 0;
}