鏈接：http://poj.org/problem?id=1743


題意：

給你n個數字，挨個作差，求這n-1個數字的最長不可重疊子串長度。

思路：

羅大牛就是6?？戳肆_牛的后綴數組PDF。這道題是后綴數組的基礎題，我們可以二分答案+判定。

如何判定？假設我們當前二分的答案是k，我們把后綴按字典序排序，同時按k分組，保證每一組內的所有的height值都>=k。這樣，如果存在長度是k的子串，一定會出現在某個組內（或者多個組，存在即可）。我們找到每個組內的sa的最小值和最大值，如果他倆的差>=k就存在這樣的解。

代碼：

#include<cstdio> #include<cstring> #include<iostream>#define maxn 20000int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} 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 check(int *sa,int n,int k) {int min=sa[1],max=sa[1];for(int i=2;i<=n;i++)//height[1]無定義,因為height[i]是sa[i]和sa[i-1]的公共前綴長度{if(height[i]<k)max=min=sa[i];else{if(sa[i]<min)min=sa[i];if(sa[i]>max)max=sa[i];if(max-min>=k)return 1;}}return 0; }int main() {freopen("in.txt","r",stdin);int r[maxn],sa[maxn];int n;while(scanf("%d",&n)!=EOF){if(!n)break;n--;int num1;scanf("%d",&num1);for(int i=0;i<n;i++){int temp;scanf("%d",&temp);r[i]=temp-num1+100;num1=temp;}r[n]=0;da(r,sa,n+1,200);calheight(r,sa,n);int min=1,max=n/2;while(min<=max){int mid=(min+max)/2;if(check(sa,n,mid))min=mid+1;elsemax=mid-1;}if(max>=4)//沒太懂為啥是4printf("%d\n",max+1);elseprintf("%d\n",0);}return 0; }

<p><strong>鏈接：</strong></p><p><a target=_blank href="http://poj.org/problem?id=1743">http://poj.org/problem?id=1743</a></p><p></p><p><strong>題意：</strong></p><p>給你n個數字，挨個作差，求這n-1個數字的最長不可重疊子串長度。</p><p></p><p><strong>思路：</strong></p><p>羅大牛就是6?？戳肆_牛的后綴數組PDF。</p><p>這道題是后綴數組的基礎題，我們可以二分答案+判定。</p><p>如何判定？假設我們當前二分的答案是k，我們把后綴按字典序排序，同時按k分組，保證每一組內的所有的height值都>=k。這樣，如果存在長度是k的子串，一定會出現在某個組內（或者多個組，存在即可）。我們找到每個組內的sa的最小值和最大值，如果他倆的差>=k就存在這樣的解。</p><p></p><p><strong>代碼：</strong></p>

總結

以上是生活随笔為你收集整理的poj1743（后缀数组：最长不可重叠子串长度）的全部內容，希望文章能夠幫你解決所遇到的問題。

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