首页 > 代码库 > 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 }
View Code

 

正解: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 }
View Code

 

本题出自USACO5.1 theme,据说是男人八题之一.....orz

poj 1743 二分答案+后缀数组 求不重叠的最长重复子串