RMQ即求區間(i,j)的最值。通過O(nlogn)處理，O(1)給出答案。

RMQ主要是動態規劃來做。dp[i][j]表示從i開始的長為2^j的區間最值。

那么可以得到dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);

dp[i][j]，這個區間可以分為2段（可以重疊），那最值就是這兩段的最值。

查詢時要找到那個j，那j=(int)(log((y-x+1)*1.0)/log(2.0));

對于求回文 可以轉變為當前的位子進行枚舉 求當前的位置的后綴和當前位置的前面部分的公共長度，又前面一部分就是在后面添加的2*n-i的位置
所以只要求出height[i+1.....2*n-i]的最小值，這里就用到RMQ來做;

#include<stdio.h> #include<math.h> #include<string.h> #include<stdlib.h> //#include<Windows.h> #define maxn 2100 #define LL long long using namespace std; int wa[maxn],wb[maxn],wv[maxn],WS[maxn],n; int dp[maxn][25]; int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} int min(int x,int y) {return x<y?x:y;} void da(int *r,int *sa,int n,int m) {int i,j,p,*x=wa,*y=wb,*t;for(i=0;i<m;i++) WS[i]=0;for(i=0;i<n;i++) WS[x[i]=r[i]]++;for(i=1;i<m;i++) WS[i]+=WS[i-1];for(i=n-1;i>=0;i--) sa[--WS[x[i]]]=i;for(j=1,p=1;p<n;j*=2,m=p){for(p=0,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<n;i++) wv[i]=x[y[i]];for(i=0;i<m;i++) WS[i]=0;for(i=0;i<n;i++) WS[wv[i]]++;for(i=1;i<m;i++) WS[i]+=WS[i-1];for(i=n-1;i>=0;i--) sa[--WS[wv[i]]]=y[i];for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;}return; } int Rank[maxn],height[maxn]; void calheight(int *r,int *sa,int n) {int i,j,k=0;for(i=1;i<=n;i++) Rank[sa[i]]=i;for(i=0;i<n;height[Rank[i++]]=k)for(k?k--:0,j=sa[Rank[i]-1];r[i+k]==r[j+k];k++);return; } int r[maxn],sa[maxn]; void RMQ() {int i,j;memset(dp,127,sizeof(dp));for(i=1;i<=2*n+1;i++)dp[i][0]=height[i];for(j=1;j<=20;j++)for(i=1;i+(1<<j)-1<=2*n+1;i++){dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);} } int lcp(int left,int right) {int a=Rank[left];int b=Rank[right];if(a>b){int t=a;a=b;b=t;}a++;int k=(int)(log((b-a+1)*1.0)/log(2.0));return min(dp[a][k],dp[b-(1<<k)+1][k]); } char s[maxn]; int main() {int i,j;scanf("%s",s);n=strlen(s);s[n]='#';int len=n+1;for(i=n-1;i>=0;i--)s[len++]=s[i];//printf("%s\n",s);for(i=0;i<2*n+1;i++)r[i]=s[i];r[2*n+1]=0;da(r,sa,n*2+2,125);calheight(r,sa,n*2+1);RMQ();int ans=-1;int set=0;int res;//對于求回文 可以轉變為當前的位子進行枚舉 求當前的位置的后綴和當前位置的前面部分的公共長度，又前面一部分就是在后面添加的2*n-i的位置//所以只要求出height[i+1.....2*n-i]的最小值for(i=0;i<n;i++){res=lcp(i,2*n-i)*2-1;//對于奇數if(res>ans){ans=res;set=i;}res=lcp(i,2*n-i+1)*2;//對于偶數if(res>ans){ans=res;set=i;}}if(ans%2){for(i=set-ans/2;i<=set+ans/2;i++){printf("%c",s[i]);}}else {for(i=set-ans/2;i<=set+ans/2-1;i++){printf("%c",s[i]);}}printf("\n");//system("pause"); }

?

轉載于:https://www.cnblogs.com/sweat123/p/4817933.html

總結

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

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