UVa 689 Napoleon‘s Grumble-育师

题目描述

给定一个文本行，找出其中所有长度至少为333的回文子串（忽略非字母字符，大小写不敏感），并按字典序输出，每个回文子串只输出一次。若一个回文子串完全包含在另一个较长的回文子串的中心位置（即两个回文中心相同且较短者完全位于较长者的中心），则较短者不应输出。例如，"AAAAAA"应输出"AAAAAA"和"AAAA"。

本题需要高效找出所有回文子串。使用Manacher\texttt{Manacher}Manacher算法可在O(n)O(n)O(n)时间内找出所有回文中心及其最大半径。然后根据半径生成所有可能的回文子串，但需过滤掉“被更长的同中心回文完全包含”的回文。由于输出要求字典序，且每个回文子串只输出一次，可以用set<string>存储所有符合条件的回文子串，最后输出。

输入格式

多行文本，每行最多102410241024个字符，以EOF\texttt{EOF}EOF结束。

输出格式

对于每行输入，输出一行，包含所有符合条件的回文子串（大写，按字典序排列），用空格分隔。若没有，输出空行。

样例

输入

As the first man said to the first woman: "Madam, I'm Adam." She responded: "Eve."

输出

TOT MADAM MADAMIMADAM DED ERE EVE

题目分析

本题要求找出所有长度至少为 3 的回文子串，但需排除“被同中心更长的回文完全包含”的回文。Manacher\texttt{Manacher}Manacher算法可以求出每个中心的最大回文半径，然后从最大回文长度向下枚举所有长度，但只需保留那些“不能由同一中心更长的回文包含”的回文。实际上，对于每个中心，只需保留最大长度的回文，因为任何较短的回文都会被最长的回文包含。但如果有多个不同中心产生的回文长度相同且内容不同，则都保留。因此，我们可以对每个中心，只考虑最大半径对应的回文，然后检查该回文是否被其他中心产生的更长的回文包含（即完全位于另一个回文的中心位置）。题目要求若一个回文完全位于另一个回文的正中心，则忽略。

解题思路

预处理：去除非字母字符，转为大写，得到字符串s。
使用Manacher\texttt{Manacher}Manacher算法计算每个中心（包括字符间空隙）的最大回文半径。
对每个中心，若最大半径对应的回文长度≥3\ge 3≥3，则生成该回文子串。
使用set<string>存储所有候选回文（去重）。
最终输出时，对于每个候选回文，检查它是否被另一个长度更长的回文完全包含在中心位置，若是则跳过。
按字典序输出所有未被排除的回文。

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，可行。

代码实现

// Napoleon's Grumble// UVa ID: 689// Verdict: Accepted// Submission Date: 2017-06-22// UVa Run Time: 0.000s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structpalindrome{intidx,length;booloperator<(constpalindrome&p)const{returnlength>p.length;}};boolcontains(set<string>&palindromes,string&block){if(palindromes.find(block)!=palindromes.end())returntrue;for(autop:palindromes){if(p.length()==block.length())continue;if((p.length()+block.length())%2==1)continue;boolincluded=true;intstart=(p.length()-block.length())/2;for(inti=0;i<block.length();i++)if(p[start+i]!=block[i]){included=false;break;}if(included)returntrue;}returnfalse;}voidmanacher(string&line){string word;word.push_back('#');for(inti=0;i<line.length();i++){word.push_back(line[i]);word.push_back('#');}vector<palindrome>P(word.size());for(inti=0;i<P.size();i++)P[i].idx=i;intcenter=0,rightmost=0,low=0,high=0;for(inti=1;i<word.length();i++){if(rightmost>i){intj=center*2-i;if(P[j].length<(rightmost-i)){P[i].length=P[j].length;low=-1;}else{P[i].length=rightmost-i;high=rightmost+1;low=i*2-high;}}else{P[i].length=0;low=i-1;high=i+1;}while(low>=0&&high<word.length()&&word[low]==word[high]){P[i].length++;low--;high++;}if((i+P[i].length)>rightmost){center=i;rightmost=i+P[i].length;}}sort(P.begin(),P.end());set<string>palindromes;for(inti=0;i<P.size();i++){if(P[i].length<=2)continue;string block;if(isalpha(word[P[i].idx]))block+=word[P[i].idx];for(intj=1;j<=P[i].length;j++)if(isalpha(word[P[i].idx+j])){block.insert(block.begin(),word[P[i].idx+j]);block.push_back(word[P[i].idx+j]);}if(contains(palindromes,block))continue;palindromes.insert(block);}boolfirst=true;for(autop:palindromes){if(first)first=false;elsecout<<' ';cout<<p;}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(inti=0;i<line.length();i++)if(isalpha(line[i]))cleared+=toupper(line[i]);manacher(cleared);}}return0;}