題目鏈接：點擊查看

題目大意：給出一個字符串，求出最長的回文子串

題目分析：如果用以往的方法求，不可避免的都需要枚舉所有子串，時間復雜度就已經到達了O(n)，而后綴數(shù)組可以通過O(n)預處理后得到所有子串的信息，我們可以利用這一點，將該字符串通過一個不同的符號，將其反轉后的字符串拼接到后面，跑完后綴數(shù)組后求一下最長公共前綴就好了，這里有兩種方法，第一種是利用height數(shù)組比較相鄰兩個sa數(shù)組，如果相鄰的兩個sa分別位于前綴和后綴，那么該height可以做出相應的貢獻，不過需要注意的是需要排除掉非對稱子串位置的影響，舉個很簡單的例子，如果不排除掉這個影響，跑zzzdanndzzz得出的答案應該是zzzd，這里只需要加上一句判斷sa[i]+sa[i-1]+height[i]==len是否成立就好了，還有一種方法比較簡單，但細節(jié)很多，就是直接用RMQ對height數(shù)組處理一下，然后直接遍歷一遍原串，對于每個位置作為回文串的中心位置，向對稱的位置求height數(shù)組就能知道以當前位置為中心的最大子串了，對于每個位置 i：

若當前需要求出偶數(shù)的回文串，則對應的位置為 n - i ，此時的長度為 2 * height[i]，起點為 i - height[i]

若當前需要求出奇數(shù)的回文串，則對應的位置為 n - i - 1 ，此時的長度為 2 * height[i] - 1，起點為?i - height[i] + 1

實時記錄一下起點和長度就好了，雖然用馬拉車也能類似的做，但是需要分奇偶，十分麻煩，或許用二分+哈希可以替代后綴數(shù)組做這一類問題，關于RMQ，有一些細節(jié)與一般的RMQ不太一樣，具體實現(xiàn)看代碼吧：

代碼：

RMQ：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=2e3+100;char str[N];int sa[N]; //SA數(shù)組，表示將S的n個后綴從小到大排序后把排好序的 //的后綴的開頭位置順次放入SA中 int t1[N],t2[N],c[N];int rk[N],height[N],len;int s[N];int st[N][25];void build_sa(int s[],int n,int m)//n為添加0后的總長 {int i,j,p,*x=t1,*y=t2;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(j=1;j<=n;j<<=1) {p=0;for(i=n-j;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];swap(x,y);p=1,x[sa[0]]=0;for(i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j]?p-1:p++;if(p>=n) break;m=p;} }void get_height(int s[],int n)//n為添加0后的總長 {int i,j,k=0;for(i=0;i<=n;i++)rk[sa[i]]=i;for(i=0;i<n;i++) {if(k) k--;j=sa[rk[i]-1];while(s[i+k]==s[j+k]) k++;height[rk[i]]=k;} }void solve(int base=128) {build_sa(s,len+1,base);get_height(s,len); }void ST_build() {for(int i=1;i<=len;i++)st[i][0]=height[i];for(int i=1;i<=log2(len);i++)for(int j=1;j+(1<<i)-1<=len;j++)st[j][i]=min(st[j][i-1],st[j+(1<<i-1)][i-1]); }int ST_query(int a,int b) {int l=rk[a],r=rk[b];if(l>r)swap(l,r);l++;int k=log2(r-l+1);return min(st[l][k],st[r-(1<<k)+1][k]); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%s",str);int lena=strlen(str);len=0;for(int i=0;str[i];i++)s[len++]=str[i];s[len++]=1;for(int i=lena-1;i>=0;i--)s[len++]=str[i];s[len]=0;solve();ST_build();int start,max_len=-inf;for(int i=0;i<lena;i++){int temp=ST_query(i,len-i-1);//回文串長度為奇數(shù) if(2*temp-1>max_len){max_len=2*temp-1;start=i-temp+1;}temp=ST_query(i,len-i);//回文串長度為偶數(shù) if(2*temp>max_len){max_len=2*temp;start=i-temp;}}for(int i=start;i<start+max_len;i++)putchar(str[i]);putchar('\n');return 0; }

?

總結

以上是生活随笔為你收集整理的URAL - 1297 Palindrome(后缀数组+RMQ)的全部內容，希望文章能夠幫你解決所遇到的問題。

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