Musical Theme poj1743(后缀数组）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 #define N 20001
 6 int a[N],c[N],d[N],e[N],sa[N],height[N],n,b[N],m;
 7 int cmp(int *r,int a,int b,int l)
 8 {
 9     return r[a]==r[b]&&r[a+l]==r[b+l];
10 }
11 void da()
12 {
13     int i,j,p,*x=c,*y=d,*t;
14     for(i=0;i<m;i++)b[i]=0;
15     for(i=0; i<n; i++)b[x[i]=a[i]]++;
16     for(i=1; i<m; i++)b[i]+=b[i-1];
17     for(i=n-1; i>=0; i--)sa[--b[x[i]]]=i;
18     for(j=1,p=1; p<n; j*=2,m=p)
19     {
20         for(p=0,i=n-j; i<n; i++)y[p++]=i;
21         for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
22         for(i=0; i<n; i++)e[i]=x[y[i]];
23         for(i=0;i<m;i++)b[i]=0;
24         for(i=0; i<n; i++)b[e[i]]++;
25         for(i=1; i<m; i++)b[i]+=b[i-1];
26         for(i=n-1; i>=0; i--)sa[--b[e[i]]]=y[i];
27         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
28             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
29     }
30 }
31 void callheight()
32 {
33     int i,j,k=0;
34     b[0]=0;
35     for(i=1; i<n; i++)b[sa[i]]=i;
36     n--;
37     for(i=0; i<n; height[b[i++]]=k)
38         for(k?k--:0,j=sa[b[i]-1]; a[i+k]==a[j+k]; k++);
39 }
40 bool check(int mid)
41 {
42     int ma,mi,i=2;
43     while(1)
44     {
45         while(i<n&&height[i]<mid)i++;
46         if(i>=n)return 0;
47         mi=ma=sa[i-1];
48         while(i<n&&height[i]>=mid)
49         {
50             ma=ma>sa[i]?ma:sa[i];
51             mi=mi<sa[i]?mi:sa[i];
52             i++;
53         }
54         if(ma-mi>=mid)return 1;
55     }
56 }
57 int main()
58 {
59     int i,l,r;
60     while(scanf("%d",&n)&&n)
61     {
62         scanf("%d",&a[0]);
63         for(i=1; i<n; i++)scanf("%d",&a[i]),a[i-1]=a[i]-a[i-1]+88,m=m<a[i-1]?a[i-1]:m;
64         m++;
65         a[n-1]=0;
66         da();
67         callheight();
68         l=4,r=n/2;
69         while(l<=r)
70         {
71             int mid=(l+r)>>1;
72             if(check(mid))
73                 l=mid+1;
74             else r=mid-1;
75         }
76        l=l>4?l:0;
77        printf("%d\n",l);
78     }
79 
80 }