本文主要是介绍Compound Words（UVA 10391），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
网址如下：
Compound Words - UVA 10391 - Virtual Judge (vjudge.net)
（第三方网站）
本来想草草了事（指随便想了个效率不是很高的算法），最后还是优化了自己的算法（怕超时）
三种算法：
第一种：把所有的可能的复合单词列出来，然后遍历判断
第二种：把所有的单词输入后，对一个单词判断时，对于每一个同开头的单词判断是否能成为这个单词的前面部分，如果可以，再判断后面部分是否存在
第三种：把所有的单词输入后，对一个单词判断时，截取单词的前面部分，判断是否存在，再判断后面部分是否存在
我用的是第三种，鉴于单词数高达120000（十二万）个，所以我认为第三种的效率更高，而且可以根据单词的最大长度和最小长度进行优化，而且可以按单词头分为26个集合
最后用时10ms
代码如下：
#include<string>
#include<cstdio>
#include<set>
#include<cctype>
using namespace std;
const int MAXALPHA = 26;
bool scanf_line(string &s);//输入word
void judgeCom(const string &s);//判断是否复合
set<string> dic[MAXALPHA];
int maxLen[MAXALPHA], minLen[MAXALPHA], maxL;int main(void)
{string s;while(scanf_line(s) && !s.empty()){int len = s.size(), loc = s[0] - 'a';dic[loc].insert(s);maxLen[loc] = (maxLen[loc] > len) ? maxLen[loc] : len;minLen[loc] = (!minLen[loc] || minLen[loc] > len) ? len : minLen[loc];s.clear();}for(int i = 0; i < MAXALPHA; i++)for(auto it = dic[i].begin(); it != dic[i].end(); it++)judgeCom(*it);return 0;
}
bool scanf_line(string &s)
{char c = getchar();if(c == EOF) return false;do{s.push_back(c);}while(isalpha(c = getchar()));if(c == EOF) return false;else return true;
}
void judgeCom(const string &s)
{int len = s.size();for(int len_f = minLen[s[0] - 'a']; len_f < len; len_f++){int len_b = len - len_f;if(len_b > maxLen[s[len_f] - 'a']) continue;string front(s, 0, len_f);if(!dic[s[0] - 'a'].count(front)) continue;string back(s, len_f);if(dic[s[len_f] - 'a'].count(back)){printf("%s\n", s.c_str()); break;}}
}因为单词数不确定，而且不知道最后一个单词末尾是否有换行符，我就写了个更具有鲁棒性的输入
这篇关于Compound Words（UVA 10391）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
