【UVa】1223 Editor

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define MAXN 5010
 6 char s[MAXN];
 7 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
 8 int sa[MAXN],height[MAXN],rk[MAXN];
 9 inline bool cmp(int *r,int a,int b,int L)
10 {
11     return r[a]==r[b]&&r[a+L]==r[b+L];
12 }
13 void SA(int n,int m)
14 {
15     int i,j,p,*x=wa,*y=wb,*t;
16     for(i=0;i<m;i++)
17         ws[i]=0;
18     for(i=0;i<n;i++)
19         ws[x[i]=s[i]]++;
20     for(i=1;i<m;i++)
21         ws[i]+=ws[i-1];
22     for(i=n-1;i>=0;i--)
23         sa[--ws[x[i]]]=i;
24     for(j=p=1;p<n;j<<=1,m=p)
25     {
26         for(p=0,i=n-j;i<n;i++)
27             y[p++]=i;
28         for(i=0;i<n;i++)
29         {
30             if(sa[i]>=j)
31                 y[p++]=sa[i]-j;
32         }
33         for(i=0;i<m;i++)
34             ws[i]=0;
35         for(i=0;i<n;i++)
36             ws[wv[i]=x[y[i]]]++;
37         for(i=1;i<m;i++)
38             ws[i]+=ws[i-1];
39         for(i=n-1;i>=0;i--)
40             sa[--ws[wv[i]]]=y[i];
41         for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i<n;i++)
42             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
43     }
44 }
45 void Height(int n)
46 {
47     int i,j,k;
48     for(i=1;i<=n;i++)
49         rk[sa[i]]=i;
50     for(i=k=0;i<n;height[rk[i++]]=k)
51         for(k?k--:0,j=sa[rk[i]-1];s[i+k]==s[j+k];k++);
52 }
53 int main()
54 {
55     int c,n,ans,i;
56     scanf("%d",&c);
57     while(c--)
58     {
59         scanf(" %s",s);
60         n=strlen(s);
61         SA(n+1,'z'+1);
62         Height(n);
63         for(ans=0,i=1;i<=n;i++)
64             ans=max(ans,height[i]);
65         printf("%d\n",ans);
66     }
67     return 0;
68 }