題意：

給出一個最多有10^5次方個數字的序列，找出其中最長的N-sequence的長度。N-sequence的定義如下：

找出原串中的一個連續的子串，分成相等的三部分，第一部分和第二部分要形成一個回文串，第二部分和第三部分要形成一個回文串，第一部分要和第三部分相等。

思路：

我們先用manacher算法在O(n)的時間內求出所有的以第i位為回文串中心的回文串的長度，然后找出每一個回文串最長能伸展到哪一位，記錄下來。然后我們枚舉以i位中心的回文串（枚舉i），每次我們在存好的set中找滿足情況離i最遠的下標，然后把i插入set，當我們枚舉的i到達了某個個回文串能伸展到的最長的位置，我們要把那個回文串中點的下標從set中刪除，如此往復，維護ans的最大值。

代碼：

#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<climits> #include<vector> #include<algorithm> #include<set>using namespace std; const int maxn=100050; vector<int> a; int rad[maxn*2]; vector<int> vec[maxn*2]; set<int> ss;void manacher() {memset(rad,0,sizeof(rad));int n = a.size();int i,j,k;i=0;j=1;while(i<n){while(i-j>=0 && i+j<n && a[i-j]==a[i+j])j++;rad[i]=j-1;k=1;while(k<=rad[i] && rad[i]-k!=rad[i-k]){rad[i+k]=min(rad[i-k],rad[i]-k);k++;}i += k;j = max(j-k,0);} }int main() { int t;scanf("%d",&t);int cas=1;while(t--){int n;scanf("%d",&n);a.clear();for (int i = 0; i < n; i++) {int x;scanf("%d", &x);a.push_back(-1);a.push_back(x);}a.push_back(-1);manacher();int len=a.size();for(int i=0;i<200040;i++)vec[i].clear();for(int i=0;i<len;i++)if(a[i]==-1)vec[i+rad[i]].push_back(i);// for (int i = 0; i < a.size(); i++) {// printf("%2d ", i);// }puts("");// for (int i = 0; i < a.size(); i++) {// printf("%2d ", a[i]);// }puts("");// for (int i = 0; i < a.size(); i++) {// printf("%2d ", rad[i]);// }puts("");int ans=0;ss.clear();for(int i=0;i<len;i++){if(a[i]==-1){int findnum=i-rad[i];// printf("i=%d find=%d\n",i,findnum);set<int>::iterator iter;// for(iter=ss.begin();iter!=ss.end();iter++)// printf("%d ",*iter);// printf("\n");iter=ss.lower_bound(findnum);if(iter!=ss.end()){int nnnn=*iter;// printf("nnn=%d\n",nnnn);int rrr=min(rad[nnnn],rad[i]);rrr=min(rrr,i-nnnn);ans=max(ans,rrr/2*3);// printf("ans=%d\n------------\n",ans);}ss.insert(i);}if(vec[i].size()!=0){for(int j=0;j<vec[i].size();j++)ss.erase(vec[i][j]);}}printf("Case #%d: ",cas++);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu5371(O(n)求回文子串的相关问题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。