题目描述给定一个文本行找出其中所有长度至少为333的回文子串忽略非字母字符大小写不敏感并按字典序输出每个回文子串只输出一次。若一个回文子串完全包含在另一个较长的回文子串的中心位置即两个回文中心相同且较短者完全位于较长者的中心则较短者不应输出。例如AAAAAA应输出AAAAAA和AAAA。本题需要高效找出所有回文子串。使用Manacher\texttt{Manacher}Manacher算法可在O(n)O(n)O(n)时间内找出所有回文中心及其最大半径。然后根据半径生成所有可能的回文子串但需过滤掉“被更长的同中心回文完全包含”的回文。由于输出要求字典序且每个回文子串只输出一次可以用setstring存储所有符合条件的回文子串最后输出。输入格式多行文本每行最多102410241024个字符以EOF\texttt{EOF}EOF结束。输出格式对于每行输入输出一行包含所有符合条件的回文子串大写按字典序排列用空格分隔。若没有输出空行。样例输入As the first man said to the first woman: Madam, Im Adam. She responded: Eve.输出TOT MADAM MADAMIMADAM DED ERE EVE题目分析本题要求找出所有长度至少为 3 的回文子串但需排除“被同中心更长的回文完全包含”的回文。Manacher\texttt{Manacher}Manacher算法可以求出每个中心的最大回文半径然后从最大回文长度向下枚举所有长度但只需保留那些“不能由同一中心更长的回文包含”的回文。实际上对于每个中心只需保留最大长度的回文因为任何较短的回文都会被最长的回文包含。但如果有多个不同中心产生的回文长度相同且内容不同则都保留。因此我们可以对每个中心只考虑最大半径对应的回文然后检查该回文是否被其他中心产生的更长的回文包含即完全位于另一个回文的中心位置。题目要求若一个回文完全位于另一个回文的正中心则忽略。解题思路预处理去除非字母字符转为大写得到字符串s。使用Manacher\texttt{Manacher}Manacher算法计算每个中心包括字符间空隙的最大回文半径。对每个中心若最大半径对应的回文长度≥3\ge 3≥3则生成该回文子串。使用setstring存储所有候选回文去重。最终输出时对于每个候选回文检查它是否被另一个长度更长的回文完全包含在中心位置若是则跳过。按字典序输出所有未被排除的回文。Manacher\texttt{Manacher}Manacher算法实现时在原字符串中插入分隔符如#以便统一处理奇偶长度回文。复杂度分析预处理O(L)O(L)O(L)Manacher\texttt{Manacher}Manacher算法O(L)O(L)O(L)回文生成和去重O(L2)O(L^2)O(L2)最坏但L≤1024L \le 1024L≤1024可行。代码实现// Napoleons Grumble// UVa ID: 689// Verdict: Accepted// Submission Date: 2017-06-22// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structpalindrome{intidx,length;booloperator(constpalindromep)const{returnlengthp.length;}};boolcontains(setstringpalindromes,stringblock){if(palindromes.find(block)!palindromes.end())returntrue;for(autop:palindromes){if(p.length()block.length())continue;if((p.length()block.length())%21)continue;boolincludedtrue;intstart(p.length()-block.length())/2;for(inti0;iblock.length();i)if(p[starti]!block[i]){includedfalse;break;}if(included)returntrue;}returnfalse;}voidmanacher(stringline){string word;word.push_back(#);for(inti0;iline.length();i){word.push_back(line[i]);word.push_back(#);}vectorpalindromeP(word.size());for(inti0;iP.size();i)P[i].idxi;intcenter0,rightmost0,low0,high0;for(inti1;iword.length();i){if(rightmosti){intjcenter*2-i;if(P[j].length(rightmost-i)){P[i].lengthP[j].length;low-1;}else{P[i].lengthrightmost-i;highrightmost1;lowi*2-high;}}else{P[i].length0;lowi-1;highi1;}while(low0highword.length()word[low]word[high]){P[i].length;low--;high;}if((iP[i].length)rightmost){centeri;rightmostiP[i].length;}}sort(P.begin(),P.end());setstringpalindromes;for(inti0;iP.size();i){if(P[i].length2)continue;string block;if(isalpha(word[P[i].idx]))blockword[P[i].idx];for(intj1;jP[i].length;j)if(isalpha(word[P[i].idxj])){block.insert(block.begin(),word[P[i].idxj]);block.push_back(word[P[i].idxj]);}if(contains(palindromes,block))continue;palindromes.insert(block);}boolfirsttrue;for(autop:palindromes){if(first)firstfalse;elsecout ;coutp;}cout\n;}intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);string line;while(getline(cin,line)){if(line.length()0)cout\n;else{string cleared;for(inti0;iline.length();i)if(isalpha(line[i]))clearedtoupper(line[i]);manacher(cleared);}}return0;}总结本题通过Manacher\texttt{Manacher}Manacher算法高效找出所有回文中心及最大半径再通过去重和中心包含关系过滤最终输出所有符合条件的回文子串。关键点包括使用Manacher\texttt{Manacher}Manacher算法处理回文查找。正确理解和实现“中心包含”过滤条件。输出时按字典序排列。该解法是回文子串问题的进阶应用适合作为字符串处理练习。