题目链接：点击查看

题目大意：给出一个字符串，求出截取前缀和后缀后拼接而成的最长回文串，前缀和后缀不能相交

题目分析：题意很简单，思路也不难想，读完题后我尝试性的看了看样例，发现前缀和后缀拼接后如果能够形成回文串，那么有一段是可以直接抵消的，比如样例 2 中的 abcdfdcecba ，我们可以分为三段来看 abcdfdcecba ，显然前缀和后缀橙色的部分是可以抵消的，但是这个字符串的答案是 abcdfdcba ，也就是说除了可以抵消的前后缀，还可能会有蓝色部分的回文前缀或回文后缀，因为前面抵消的部分比较简单，写个双指针乱搞一下就出来了，所以现在问题就转换为了，如何求最长回文前缀或最长回文后缀

最长回文前缀和后缀，之前我是做过一个类似的题目，用马拉车解决的，时间复杂度O(n)，且常数小，只需要在内部判断一下是否为前缀或后缀就好了

或者可以直接用回文自动机，O(n)建树然后 len[ last ] 就是最长回文后缀，简单无脑。。虽然有点杀鸡用牛刀，但毕竟不用动脑子也不用改模板呀，还是比较舒服的

还有一种方法是二分+哈希，首先时间复杂度 nlogn ，相对于上面两种方法就稍逊一点了，再加上这是cf，太容易被hack了，属实不推荐

代码：

马拉车：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char ss[N];char s[N*2];//预处理之后的字符串char str[N];//原本的字符串int p[N*2];//最长回文半径bool front;int Manacher() {int k=0;s[k++]='!';for(int i=0;str[i];i++){s[k++]='#';s[k++]=str[i];}s[k++]='#';s[k]=0;int ans=0;p[0]=1;int id=0,mmax=0;for(int i=1;i<k;i++){if(i<mmax)p[i]=min(mmax-i,p[2*id-i]);elsep[i]=1;while(s[i-p[i]]==s[i+p[i]])p[i]++;if(i+p[i]>mmax){mmax=i+p[i];id=i;}if(i+p[i]==k||p[i]==i){if(ans>=p[i]-1)continue;ans=p[i]-1;if(i+p[i]==k)//后缀front=false;if(p[i]==i)//前缀front=true;}}return ans; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",ss+1);int n=strlen(ss+1);int l=1,r=n;deque<char>ans1,ans2;while(l<r&&ss[l]==ss[r]){ans1.push_back(ss[l]);ans2.push_front(ss[r]);l++,r--;}for(int i=l;i<=r;i++)str[i-l]=ss[i];str[r-l+1]=0;int len=Manacher();for(int i=0;i<ans1.size();i++)putchar(ans1[i]);if(front)for(int i=l;i<len+l;i++)putchar(ss[i]);elsefor(int i=r-len+1;i<=r;i++)putchar(ss[i]);for(int i=0;i<ans2.size();i++)putchar(ans2[i]);putchar('\n');}return 0; }

回文自动机：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];int n;struct Palindrome_tree {int nxt[N][26];int fail[N]; // 当前节点最长回文后缀的节点int len[N]; // 当前节点表示的回文串的长度int cnt[N]; // 当前节点回文串的个数， 在getcnt后可得到全部int sed[N]; // 以当前节点为后缀的回文串的个数（并不是表示第i结尾的回文串的种类数，如果要求每个点结尾的数的回文串个数，得用last）int record[N]; //record记录了节点回文串的结束位置char s[N];int tot; // 节点个数int last; // 上一个节点int n;//当前字符串的长度 void newnode(){tot++;memset(nxt[tot],0,sizeof(nxt[tot]));cnt[tot]=sed[tot]=len[tot]=fail[tot]=0;}void init(){n=0;tot=-1;newnode();newnode();len[0] = 0, len[1] = -1; // 0为偶数长度根， 1为奇数长度根tot = 1, last = 0;fail[0] = 1;}int getfail(int x, int n){while (s[n - len[x] - 1] != s[n]||n-len[x]-1<0) // 比较x节点回文串新建两端是否相等//n-len[x]-1<0这个是我自己加的，多组的时候光第一个条件是不够的，所以有错请手动删除x = fail[x]; // 若不同， 再比较x后缀回文串两端return x;}void insert(char ch){int c = ch - 'a';//全小写要用a 全大写要用A 不然会错s[++n]=ch;int p = getfail(last, n);// 得到第i个字符可以加到哪个节点的两端形成回文串if (!nxt[p][c]){newnode();len[tot] = len[p] + 2; // 在p节点两端添加两个字符fail[tot] = nxt[getfail(fail[p], n)][c]; //tot点的后缀回文，可以由上一个节点的后缀回文尝试得到sed[tot] = sed[fail[tot]] + 1; // 以当前节点为结尾的回文串个数nxt[p][c] = tot; // 新建节点}last = nxt[p][c]; // 当前节点成为上一个节点cnt[last]++; //当前节点回文串++record[last] = n;}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];//fail[i] 的节点 为 i 节点的后缀回文串， 所以个数相加} }tree;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){scanf("%s",s+1);n=strlen(s+1);int l=1,r=n;deque<char>ans1,ans2;while(l<r&&s[l]==s[r]){ans1.push_back(s[l]);ans2.push_front(s[r]);l++,r--;}bool front;int len=0;tree.init();for(int i=l;i<=r;i++)tree.insert(s[i]);if(tree.len[tree.last]>len){len=tree.len[tree.last];front=false;}tree.init();for(int i=r;i>=l;i--)tree.insert(s[i]);if(tree.len[tree.last]>len){len=tree.len[tree.last];front=true;}for(int i=0;i<ans1.size();i++)putchar(ans1[i]);if(front)for(int i=l;i<len+l;i++)putchar(s[i]);elsefor(int i=r-len+1;i<=r;i++)putchar(s[i]);for(int i=0;i<ans2.size();i++)putchar(ans2[i]);putchar('\n');}return 0; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 1326D2 Prefix-Suffix Palindrome (Hard version)(马拉车/回文自动机)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。