首页 > 代码库 > POJ 1743 (后缀数组+不重叠最长重复子串)
POJ 1743 (后缀数组+不重叠最长重复子串)
题目链接: http://poj.org/problem?id=1743
题目大意：楼教主の男人八题orz。一篇钢琴谱，每个旋律的值都在1~88以内。琴谱的某段会变调，也就是说某段的数可以加减一个旋律范围的值。问这个谱子内最长不重叠的重复部分大小。
解题思路：
网上题解已经泛滥的题。很多细节都被先辈大神总结了。
在当年后缀数组还不是热门的时候，这题确实是神题。
首先对于旋律变调的处理：
比如123，123，ans=3。
变调之后：456,123，ans=0？不ans=3。
所以不能使用旋律的初始值。应该取每个旋律前后的差值，这样就能保证某段无论怎么变调，都和原来一样。
不过这样就变成n-1个旋律，并且ans会-1，可以拿笔算几组看看。
对于取差值后的n-1个旋律，计算SA和LCP。 PS。很多人SA模板都是有问题的，并且推荐自动末尾补0的SA模板，不容易出现问题。
要求不重叠的重复部分大小，这里套用网上被传承N遍的奇葩结论：
将height数组分组，每组内的后缀之间的height都要大于len，如果每组内的后缀之间的最长公共前缀有大于len的而且这两个后缀的SA之差大于len就说明存在长度至少为len的不重复子串。求最长公共前缀就要用到height数组，因为这组中任意两个后缀的公共前缀必定是某些height值中的最小值，而这个值如果最大则一定是这组中height中的最大值。
由于SA数组按字典序来的，二分SA数组长度。如果len符合要求，则先记录。再向右找更大的，否则向左。注意二分的时候ans初始值为0，不然当n=1的时候，等于没有二分就return了一个ans。
#include "cstring"#include "cstdio"#include "string"#include "iostream"using namespace std;#define maxn 23000int n,r[maxn],tmp[maxn];template <class T>inline bool read(T &ret){ char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar(); sgn=(c==‘-‘)?-1:1; ret=(c==‘-‘)?0:(c-‘0‘); while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘); ret*=sgn; return 1;}struct Suffix{ int sa[maxn],rk[maxn],height[maxn]; int t[maxn],t2[maxn],c[maxn],m; void init() {m=200;} int cmp(int *r,int a,int b,int l) {return r[a]==r[b]&&r[a+l]==r[b+l];} void build() { int i,k,p,*x=t,*y=t2; r[n++]=0; for (i=0; i<m; i++) c[i]=0; for (i=0; i<n; i++) c[x[i]=r[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 (k=1,p=1; k<n; k*=2,m=p) { for (p=0,i=n-k; i<n; i++) y[p++]=i; for (i=0; i<n; i++) if (sa[i]>=k) y[p++]=sa[i]-k; 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]]=cmp(y,sa[i-1],sa[i],k)?p-1:p++; } n--; } void LCP() { int i,j,k=0; for (i=1; i<=n; i++) rk[sa[i]]=i; for (i=0; i<n; i++) { if (k) k--; j=sa[rk[i]-1]; while (r[i+k]==r[j+k]) k++; height[rk[i]]=k; } } bool judge(int len) { int l=sa[1],r=sa[1]; for(int i=2;i<=n;i++) { if(height[i]<len) { l=sa[i];r=sa[i]; continue; } l=min(l,sa[i]); r=max(r,sa[i]); if(r-l>len) return true; } return false; } int BinarySearch() { int l=0,r=n,mid,ans=0;//注意ans=0，不然当n=1的时候返回的是没赋值的ans while(l<=r) { int mid=l+(r-l)/2; if(judge(mid)) {ans=mid;l=mid+1;} else r=mid-1; } return ans; }};int main(){ //freopen("in.txt","r",stdin); //freopen("out1.txt","w",stdout); while(read(n)&&n) { for(int i=0; i<n; i++) read(tmp[i]); for(int i=0; i<n-1; i++) {r[i]=tmp[i+1]-tmp[i]+90;} Suffix a; a.init(); a.build(); a.LCP(); int ans=a.BinarySearch(); if(ans<4) printf("0\n"); else printf("%d\n",ans+1); }}
| 13560509 | neopenx | 1743 | Accepted | 840K | 407MS | C++ | 2761B | 2014-10-24 10:20:38 |
POJ 1743 (后缀数组+不重叠最长重复子串)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。