1297. Palindrome ural1297（后缀数组）

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <math.h>
 4 #include <string.h>
 5 using namespace std;
 6 #define N 2005
 7 char a[N],bb[N];
 8 int c[N],d[N],e[N],sa[N],height[N],n,b[N],m,dp[N][12];
 9 int 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 da()
14 {
15     int i,j,p,*x=c,*y=d,*t;
16     memset(b,0,sizeof(b));
17     for(i=0; i<n; i++)b[x[i]=a[i]]++;
18     for(i=1; i<m; i++)b[i]+=b[i-1];
19     for(i=n-1; i>=0; i--)sa[--b[x[i]]]=i;
20     for(j=1,p=1; p<n; j*=2,m=p)
21     {
22         for(p=0,i=n-j; i<n; i++)y[p++]=i;
23         for(i=0; i<n; i++)if(sa[i]>=j)y[p++]=sa[i]-j;
24         for(i=0; i<n; i++)e[i]=x[y[i]];
25         for(i=0; i<m; i++)b[i]=0;
26         for(i=0; i<n; i++)b[e[i]]++;
27         for(i=1; i<m; i++)b[i]+=b[i-1];
28         for(i=n-1; i>=0; i--)sa[--b[e[i]]]=y[i];
29         for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++)
30             x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
31     }
32 }
33 void callheight()
34 {
35     int i,j,k=0;
36     b[0]=0;
37     for(i=1; i<n; i++)b[sa[i]]=i;
38     for(i=0; i<n-1; height[b[i++]]=k)
39         for(k?k--:0,j=sa[b[i]-1]; a[i+k]==a[j+k]; k++);
40 }
41 int fun(int i,int j)
42 {
43     i=b[i];
44     j=b[j];
45     if(i>j)swap(i,j);
46     i++;
47     int k=(int)(log(j-i+1.0)/log (2.0));
48     return min(dp[i][k],dp[j-(1<<k)+1][k]);
49 }
50 void initrmq()
51 {
52     int i,j;
53     memset(dp,0,sizeof(dp));
54     for(i=0; i<=n; i++)
55         dp[i][0]=height[i];
56     for(j=1; (1<<j)<=n; j++)
57         for(i=0; i+(1<<j)<=n; i++)
58             dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
59 }
60 int main()
61 {
62     m=200;
63     scanf("%s",a);
64     int size=n=strlen(a);
65     strcpy(bb,a);
66     a[n]=‘#‘;
67     strrev(bb);
68     strcat(a,bb);
69     n=strlen(a);
70     a[n++]=‘\0‘;
71     da();
72     callheight();
73     n--;
74     initrmq();
75     int maxa=0,maxi=0;
76     for(int i=0; i<size; i++)
77     {
78         int tt=fun(i,n-i);
79         if((tt<<1)>maxa)
80         {
81             maxa=tt<<1;
82             maxi=i-tt;
83         }
84         tt=fun(i,n-i-1);
85         if((tt<<1)-1>maxa)
86         {
87             maxa=(tt<<1)-1;
88             maxi=i-(--tt);
89         }
90     }
91     for(int i=0; i<maxa; i++)
92         putchar(a[i+maxi]);
93    putchar(‘\n‘);
94 }