首页 > 代码库 > poj 1743 最长不重叠重复子串 后缀数组+lcp+二分
poj 1743 最长不重叠重复子串 后缀数组+lcp+二分
题比较容易读懂,但是建模需动点脑子:
一个子串加常数形成的子串认为跟子串相同,求最长不重叠重复子串
题目中说
- is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)
意味着不能重叠,举个例子
1, 2,3, 52, 53,54
1,2, 3和 52, 53,54满足题意,差值为51
枚举差值肯定不行------看了题解明白的::
后项减去前一项得到: 1,1,1,49,1,1 注意此时答案是2+1,
如果按这种推法
1, 2,3, 52, 53,54,55
后项减去前一项得到: 1,1,1,49,1,1 ,1 答案是3+1,肯定是错的!
为了排除第一项的干扰,把第一项删去或者把后面的项同时加上>88的数,或者作差后直接把第一项删去
这道题学到的思想-----相邻项作差消去增量
#include <cstdio> #include <iostream> #include <string> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 20200; int rk[MAXN],sa[MAXN],s[MAXN],tmp[MAXN],lcp[MAXN],n,k; bool cmpSa(int i,int j) { if(rk[i] != rk[j])return rk[i]<rk[j]; else { int ri = i+k<=n?rk[i+k]:-1; int rj = j+k<=n?rk[j+k]:-1; return ri<rj; } } void consa() { for(int i=0;i<=n;i++) sa[i]=i,rk[i]=i<n?s[i]:-1; for(k=1;k<=n;k*=2) { sort(sa,sa+n+1,cmpSa); tmp[sa[0]]=0; for(int i=1;i<=n;i++) { tmp[sa[i]]=tmp[sa[i-1]]+(cmpSa(sa[i-1],sa[i])?1:0); } for(int i=0;i<=n;i++) rk[i]=tmp[i]; } } void construct_lcp() { //n=strlen(s); for(int i=0; i<=n; i++)rk[sa[i]]=i; int h=0; lcp[0]=0; for(int i=0;i<n;i++) { int j=sa[rk[i]-1]; if(h>0)h--; for(; j+h<n && i+h<n; h++) { if(s[j+h]!=s[i+h])break; } lcp[rk[i]-1]=h; } } int C(int x) { int ret=0,last=0,mmin=n,mmax=0; for(int i=0;i<=n;i++) { if(lcp[i]>=x) { ret++; mmin=min(sa[i],min(mmin,sa[i+1])); mmax=max(sa[i],max(mmax,sa[i+1])); } else { if(i>=1 && (mmax-mmin) >=x)return 1;////////////////// ret=mmax=0; mmin=n; } } return 0; } int main() { //freopen("poj 1743.txt","r",stdin); int t; while(scanf("%d",&n)!=EOF && n) { for(int i=0;i<n;i++) scanf("%d",&s[i]); /*for(int i=1;i<n;i++) s[i]=s[i]-s[i-1];*/ for(int i=n-1;i>=1;i--) s[i]=s[i]-s[i-1]+100; s[n]=-200; //s[0]=-111900; consa(); construct_lcp(); ////////////////////// //for(int i=0;i<=n;i++) // printf("sa[i]=%d lcp[%d]=%d\n", sa[i],i,lcp[i]); ///////////////////// int d=0,up=n+1,mid; while(up>d+1) { mid=(d+up)/2; if(C(mid))d=mid; else up=mid; } if(d>=4) printf("%d\n",d+1); else printf("0\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。