poj1743 Musical Theme
1#include
2#include 3#include 4#include 5 6constintN =20005; 7int sa[N],s[N],wa[N], wb[N], ws[N], wv[N]; 8int rank[N], height[N]; 910boolcmp(intr[],inta,intb,int l)11{12returnr[a] == r[b] && r[a+l] == r[b+l];13}1415voidda(intr[],intsa[],intn,int m)16{17inti, j, p, *x = wa, *y = wb;18for(i =0; i < m; ++i) ws[i] =0;19for(i =0; i < n; ++i) ws[x[i]=r[i]]++;20for(i =1; i < m; ++i) ws[i] += ws[i-1];21for(i = n-1; i >=0; --i) sa[--ws[x[i]]] = i;22for(j =1, p =1; p < n; j *=2, m = p)23 {24for(p =0, i = n - j; i < n; ++i) y[p++] = i;25for(i =0; i < n; ++i)if(sa[i] >= j) y[p++] = sa[i] - j;26for(i =0; i < n; ++i) wv[i] = x[y[i]];27for(i =0; i < m; ++i) ws[i] =0;28for(i =0; i < n; ++i) ws[wv[i]]++;29for(i =1; i < m; ++i) ws[i] += ws[i-1];30for(i = n-1; i >=0; --i) sa[--ws[wv[i]]] = y[i];31for(std::swap(x, y), p =1, x[sa[0]] =0, i =1; i < n; ++i)32x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1: p++;33 }34}3536voidcalheight(intr[],intsa[],int n)37{38inti, j, k =0;39for(i =1; i <= n; ++i) rank[sa[i]] = i;40for(i =0; i < n; height[rank[i++]] = k)41for(k?k--:0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k++);42}43boolcheck(intlen,int x)44{45intmx=sa[1],mi=sa[1];46for(inti=2;i<=len;i++)47 {48if(height[i]<x)49 {50if(mx-mi>=x)51return1;52mx=mi=sa[i];53 }54else55 {56mx=std::max(sa[i],mx);57mi=std::min(sa[i],mi);58 }59 }60returnmx-mi>=x;61}62int main()63{64int n;65while(scanf("%d",&n)&&n)66 {67intx,ls,len=0;68scanf("%d",&ls);69for(inti=0;i1;i++)70scanf("%d",&x),s[len++]=x-ls+100,ls=x;71s[len]=0;72da(s,sa,len+1,200);73 calheight(s,sa,len);74intl=5,r=n/2,ans=0;75while(l<=r)76 {77intmid=l+r>>1;78if(check(len,mid-1))79ans=mid,l=mid+1;80else81r=mid-1;82 }83printf("%d\n",ans);84 }85return0;86}
来源: http://www.bubuko.com/infodetail-2002325.html