首页 > 代码库 > poj 1743 二分答案+后缀数组 求不重叠的最长重复子串
poj 1743 二分答案+后缀数组 求不重叠的最长重复子串
题意:给出一串序列,求最长的theme长度
(theme:完全重叠的子序列,如1 2 3和1 2 3 or 子序列中每个元素对应的差相等,如1 2 3和7 8 9)
要是没有差相等这个条件那就好办多了,直接裸题。
一开始想了个2B方法,后来发现真心2B啊蛤蛤蛤
1 for i=1 to 88 do 2 { 3 for j=1 to length 4 { 5 r2[j]=r[j]+i; 6 if (r2[j]>88) r2[i]-=88; 7 } 8 把新序列r2连接到原序列r的后面 9 process[r+r2]10 .....11 求for i=1->88中得到的最大答案 12 }
正解:http://bbezxcy.iteye.com/blog/1407395
对原序列相邻两元素作差就行了= =
比如:序列8 8 8 15 24 3 3 3
作差得到0 0 7 9 -21 0 0
对新序列再求最长不重叠重复子串,得到的结果+1,就是原序列的最长不重叠重复子串
求最长不重叠重复子串:参考IOI2009论文
Code:
1 #include "stdio.h" 2 #include "string.h" 3 #define maxn 20010 4 5 int wa[maxn],wb[maxn],wv[maxn],ws[maxn]; 6 int rank[maxn],height[maxn]; 7 int r[maxn],sa[maxn],ans[maxn]; 8 int n; 9 10 11 int cmp(int *r,int a,int b,int l) 12 { 13 return r[a]==r[b]&&r[a+l]==r[b+l]; 14 } 15 16 void da(int *r,int *sa,int n,int m) 17 { 18 int i,j,p,*x=wa,*y=wb,*t; 19 for(i=0; i<m; i++) ws[i]=0; 20 for(i=0; i<n; i++) ws[x[i]=r[i]]++; 21 for(i=1; i<m; i++) ws[i]+=ws[i-1]; 22 for(i=n-1; i>=0; i--) sa[--ws[x[i]]]=i; 23 for(j=1,p=1; p<n; j*=2,m=p) 24 { 25 26 for(p=0,i=n-j; i<n; i++) y[p++]=i; 27 for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j; 28 for(i=0; i<n; i++) wv[i]=x[y[i]]; 29 for(i=0; i<m; i++) ws[i]=0; 30 for(i=0; i<n; i++) ws[wv[i]]++; 31 for(i=1; i<m; i++) ws[i]+=ws[i-1]; 32 for(i=n-1; i>=0; i--) sa[--ws[wv[i]]]=y[i]; 33 for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++) 34 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 35 } 36 return; 37 } 38 39 void calheight(int *r,int *sa,int n) 40 { 41 int i,j,k=0; 42 for(i=1; i<=n; i++) rank[sa[i]]=i; 43 for(i=0; i<n; height[rank[i++]]=k) 44 for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++); 45 return; 46 } 47 48 bool calc(int x) 49 { 50 int nm=0; 51 for (int i=1;i<=n;i++) 52 if (height[i]<x) 53 { 54 nm++; 55 ans[nm]=i; 56 } 57 nm++; 58 ans[nm]=n+1; 59 for (int i=0;i<nm;i++) 60 { 61 int tl=ans[i],tr=ans[i+1]-1; 62 int tn=maxn,tx=0; 63 for (int j=tl;j<=tr;j++) 64 { 65 if (tn>sa[j]) tn=sa[j]; 66 if (tx<sa[j]) tx=sa[j]; 67 } 68 if (tx-tn>=x) return true; 69 } 70 return false; 71 } 72 73 //da(r,sa,n+1,128); 74 //calheight(r,sa,n); 75 int main() 76 { 77 // freopen("in.txt","r",stdin); 78 while (~scanf("%d",&n)) 79 { 80 if (n!=0) 81 { 82 memset(sa,0,sizeof(sa)); 83 memset(height,0,sizeof(height)); 84 memset(ans,0,sizeof(ans)); 85 86 for (int i=0; i<n; i++) 87 scanf("%d",&r[i]); 88 r[n]=0; 89 90 // for (int i=0;i<=n;i++) 91 // printf("%d ",r[i]); 92 // printf("\n %d\n",n); 93 94 for (int i=1;i<n;i++) 95 r[i-1]=r[i]-r[i-1]; 96 n--; 97 r[n]=0; 98 99 for (int i=0;i<n;i++)100 r[i]+=100;101 102 // for (int i=0;i<=n;i++)103 // printf("%d ",r[i]);104 // printf("\n %d\n",n);105 106 da(r,sa,n+1,200);107 calheight(r,sa,n);108 109 // for (int i=0; i<=n; i++)110 // printf("%d %d\n",sa[i],height[i]);111 // printf("\n");112 113 int l=maxn,r=0,res=0;114 for (int i=1;i<=n;i++)115 {116 if (height[i]<l) l=height[i];117 if (height[i]>r) r=height[i];118 }119 while (r>=l)120 {121 int mid=(l+r)/2;122 if (calc(mid))123 {124 l=mid+1;125 res=mid;126 }127 else128 r=mid-1;129 }130 res++;131 if (res<5) res=0;132 printf("%d\n",res);133 }134 }135 return 0;136 }
本题出自USACO5.1 theme,据说是男人八题之一.....orz
poj 1743 二分答案+后缀数组 求不重叠的最长重复子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。