题意：给出一串序列，求最长的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(" %d ",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(" %d ",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 ",sa[i],height[i]); 111 // printf(" "); 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 else 128 r=mid-1; 129 } 130 res++; 131 if (res<5) res=0; 132 printf("%d ",res); 133 } 134 } 135 return 0; 136 }
本题出自USACO5.1 theme，据说是男人八题之一.....orz