題目鏈接：點擊查看

題目大意：給出一個字符串，求出截取前綴和后綴后拼接而成的最長回文串，前綴和后綴不能相交

題目分析：題意很簡單，思路也不難想，讀完題后我嘗試性的看了看樣例，發(fā)現(xiàn)前綴和后綴拼接后如果能夠形成回文串，那么有一段是可以直接抵消的，比如樣例 2 中的 abcdfdcecba ，我們可以分為三段來看?abcdfdcecba ，顯然前綴和后綴橙色的部分是可以抵消的，但是這個字符串的答案是 abcdfdcba ，也就是說除了可以抵消的前后綴，還可能會有藍色部分的回文前綴或回文后綴，因為前面抵消的部分比較簡單，寫個雙指針亂搞一下就出來了，所以現(xiàn)在問題就轉(zhuǎn)換為了，如何求最長回文前綴或最長回文后綴

最長回文前綴和后綴，之前我是做過一個類似的題目，用馬拉車解決的，時間復(fù)雜度O(n)，且常數(shù)小，只需要在內(nèi)部判斷一下是否為前綴或后綴就好了

或者可以直接用回文自動機，O(n)建樹然后 len[ last?] 就是最長回文后綴，簡單無腦。。雖然有點殺雞用牛刀，但畢竟不用動腦子也不用改模板呀，還是比較舒服的

還有一種方法是二分+哈希，首先時間復(fù)雜度 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];//預(yù)處理之后的字符串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]; // 當(dāng)前節(jié)點最長回文后綴的節(jié)點int len[N]; // 當(dāng)前節(jié)點表示的回文串的長度int cnt[N]; // 當(dāng)前節(jié)點回文串的個數(shù)， 在getcnt后可得到全部int sed[N]; // 以當(dāng)前節(jié)點為后綴的回文串的個數(shù)（并不是表示第i結(jié)尾的回文串的種類數(shù)，如果要求每個點結(jié)尾的數(shù)的回文串個數(shù)，得用last）int record[N]; //record記錄了節(jié)點回文串的結(jié)束位置char s[N];int tot; // 節(jié)點個數(shù)int last; // 上一個節(jié)點int n;//當(dāng)前字符串的長度 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為偶數(shù)長度根， 1為奇數(shù)長度根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節(jié)點回文串新建兩端是否相等//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個字符可以加到哪個節(jié)點的兩端形成回文串if (!nxt[p][c]){newnode();len[tot] = len[p] + 2; // 在p節(jié)點兩端添加兩個字符fail[tot] = nxt[getfail(fail[p], n)][c]; //tot點的后綴回文，可以由上一個節(jié)點的后綴回文嘗試得到sed[tot] = sed[fail[tot]] + 1; // 以當(dāng)前節(jié)點為結(jié)尾的回文串個數(shù)nxt[p][c] = tot; // 新建節(jié)點}last = nxt[p][c]; // 當(dāng)前節(jié)點成為上一個節(jié)點cnt[last]++; //當(dāng)前節(jié)點回文串++record[last] = n;}void get_cnt(){for (int i = tot; i > 0; i--)cnt[fail[i]] += cnt[i];//fail[i] 的節(jié)點 為 i 節(jié)點的后綴回文串， 所以個數(shù)相加} }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; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1326D2 Prefix-Suffix Palindrome (Hard version)(马拉车/回文自动机)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。