UVa 257 Palinwords

题目分析本题要求从输入文件中筛选出符合特定条件的单词称为 “Palinwords”并将其按出现顺序输出到输出文件中。每个单词由大写字母组成长度不超过255255255个字符。一个单词成为Palinword需要满足以下条件单词中包含至少两个不同的回文子串每个回文子串的长度至少为333。这两个回文子串不能相互包含即一个不能是另一个的子串但可以部分重叠。相同内容但出现在不同位置的回文子串视为同一个回文子串位置无关。示例说明题目描述中提到回文mum被嵌入在回文amuma中因为amuma包含了mum作为连续子串。回文aaa被嵌入在回文aaaa中同样存在包含关系。因此如果一个单词中只有aaaa这一个长度为333以上的回文它不满足条件因为需要两个不同的回文且它们不能相互包含。输入输出格式输入文本文件每行包含若干由空格分隔的单词全大写字母每行最多255255255个字符可能包含空行。输出每行一个符合条件的Palinword按输入顺序输出。样例分析输入MOEILIJKHEDEN INVOER VERNEDEREN AMUMA AMAMA MUMMUM AMATRAMA AAAA ABATRABAR DUMMY WORDS输出MOEILIJKHEDEN VERNEDEREN AMAMA MUMMUM解题思路核心问题我们需要判断一个单词中是否存在两个不同且互不包含的长度至少为333的回文子串。方法一朴素枚举最直接的想法是枚举所有长度≥3\ge 3≥3的回文子串然后检查是否存在满足条件的一对。但单词长度最大为255255255枚举所有子串的时间复杂度为O(n3)O(n^3)O(n3)其中nnn是单词长度。n255n255n255时n3≈1.66×107n^3 \approx 1.66 \times 10^7n3≈1.66×107配合回文判断可能勉强能过但不是最优解。方法二Manacher\texttt{Manacher}Manacher算法Manacher\texttt{Manacher}Manacher算法可以在O(n)O(n)O(n)时间内找出字符串中的所有回文子串以每个位置为中心的最长回文半径。利用Manacher\texttt{Manacher}Manacher算法我们可以高效地提取所有长度≥3\ge 3≥3的回文子串。算法步骤预处理在原字符串的每个字符之间和两端插入分隔符如#使得奇偶长度的回文都能统一处理。计算回文半径数组P[i]P[i]P[i]表示以位置iii为中心的最长回文半径。收集回文子串遍历每个中心位置根据P[i]P[i]P[i]可以生成从长度333到最长半径的所有回文子串。注意只收集长度≥3\ge 3≥3的回文。去重与判重使用集合存储已经发现的不同回文子串。当发现一个新的回文时检查它与集合中已有的每个回文是否互不包含。若存在这样的一对则当前单词是Palinword立即返回true\texttt{true}true。回文互不包含的判断对于两个字符串AAA和BBB判断它们互不包含的条件是AAA不是BBB的子串且BBB不是AAA的子串。在代码中使用string::find方法if(palindrome.find(*it)palindrome.npos(*it).find(palindrome)palindrome.npos)如果find返回npos表示未找到即不包含。算法复杂度预处理O(n)O(n)O(n)遍历生成回文最坏情况下每个中心可能生成O(P[i])O(P[i])O(P[i])个回文但总回文数实际上O(n2)O(n^2)O(n2)级别。不过由于n255n255n255且我们只考虑长度≥3\ge 3≥3的回文且一旦找到符合条件的两个回文就提前终止实际运行很快。使用集合存储回文插入和查找为O(log⁡m)O(\log m)O(logm)其中mmm为已发现的不同回文数量。代码实现// Palinwords// UVa ID: 257// Verdict: Accepted// Submission Date: 2016-05-16// UVa Run Time: 0.020s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 判断一个单词是否为 Palinwordboolmanacher(string word){// 在字符之间插入 #将奇偶长度的回文统一处理for(intiword.length()-1;i0;i--)word.insert(word.begin()i,#);word.push_back(#);// 在末尾也添加分隔符方便边界处理vectorintP(word.size());// 回文半径数组setstringpalindromes;// 存储已发现的不同回文子串长度3intcenter0,rightmost0,low0,high0;for(inti1;iword.length();i){// 利用之前计算的信息进行优化if(rightmosti){intjcenter*2-i;// i 关于 center 的对称点if(P[j](rightmost-i)){P[i]P[j];low-1;// 标记不需要扩展}else{P[i]rightmost-i;highrightmost1;lowi*2-high;}}else{P[i]0;lowi-1;highi1;}// 中心扩展计算以 i 为中心的最长回文半径while(low0highword.length()word[low]word[high]){P[i];low--;high;}// 更新最右边界和对应的中心if((iP[i])rightmost){centeri;rightmostiP[i];}// 如果当前中心存在长度 3 的回文if(P[i]3){string palindrome;// 中心字符可能是字母或 #只取字母if(isalpha(word[i]))palindromeword[i];// 从中心向外扩展逐步构造回文子串// 注意这里构造的是回文的右半部分同时向左镜像补充for(intji1;j(iP[i]-1);j)if(isalpha(word[j])){palindromeword[j];palindrome.insert(palindrome.begin(),word[j]);// 只需要检查长度在 3 到 4 之间的回文// 因为如果一个长度 5 的回文存在它内部必然包含长度 3 或 4 的回文// 而且题目要求两个回文互不包含检查较短的即可if(palindrome.length()5)break;if(palindrome.length()3){// 去重如果已经存在这个回文跳过if(palindromes.count(palindrome)0)continue;// 检查新回文是否与已有回文互不包含for(autoitpalindromes.begin();it!palindromes.end();it)// 两个条件新回文不包含已有回文且已有回文不包含新回文if(palindrome.find(*it)palindrome.npos(*it).find(palindrome)palindrome.npos)returntrue;// 找到一对即为 Palinword// 将当前回文加入集合palindromes.insert(palindrome);}}}}returnfalse;// 未找到符合条件的两个回文}intmain(){string line;while(getline(cin,line)){if(line.length()0)continue;// 跳过空行string word;istringstreamiss(line);while(issword)if(manacher(word))coutword\n;// 输出 Palinword}return0;}关键优化说明代码中只检查长度在333到444之间的回文这是因为如果一个长度≥5\ge 5≥5的回文存在它内部必然包含长度为333或444的回文例如abcba包含bcb。题目要求的是存在两个互不包含的回文因此只需要考虑短回文即可这样可以大大减少需要检查的回文数量。总结本题的核心是高效地找出字符串中的所有回文子串并判断是否存在两个互不包含的长度至少为333的回文子串。使用Manacher\texttt{Manacher}Manacher算法可以在O(n)O(n)O(n)时间内获取所有回文信息配合集合去重和子串包含检查能够快速完成判断。代码实现时要注意边界条件和回文构造的逻辑。