1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 #define MAXN 2200
6 #define MAXM 12
7 char s[MAXN],t[MAXN];
8 int wa[MAXN],wb[MAXN],wv[MAXN],ws[MAXN];
9 int sa[MAXN],rk[MAXN],height[MAXN];
10 int st[MAXN][MAXM];
11 inline
bool cmp(
int *r,
int a,
int b,
int len)
12 {
13 return r[a]==r[b]&&r[a+len]==r[b+
len];
14 }
15 void SA(
int n,
int m)
16 {
17 int i,j,p,*x=wa,*y=wb,*
t;
18 for(i=
0;i<m;i++
)
19 ws[i]=
0;
20 for(i=
0;i<n;i++
)
21 ws[x[i]=s[i]]++
;
22 for(i=
1;i<m;i++
)
23 ws[i]+=ws[i-
1];
24 for(i=n-
1;i>=
0;i--
)
25 sa[--ws[x[i]]]=
i;
26 for(j=p=
1;p<n;j<<=
1,m=
p)
27 {
28 for(p=
0,i=n-j;i<n;i++
)
29 y[p++]=
i;
30 for(i=
0;i<n;i++
)
31 {
32 if(sa[i]>=
j)
33 y[p++]=sa[i]-
j;
34 }
35 for(i=
0;i<m;i++
)
36 ws[i]=
0;
37 for(i=
0;i<n;i++
)
38 ws[wv[i]=x[y[i]]]++
;
39 for(i=
1;i<m;i++
)
40 ws[i]+=ws[i-
1];
41 for(i=n-
1;i>=
0;i--
)
42 sa[--ws[wv[i]]]=
y[i];
43 for(t=x,x=y,y=t,x[sa[
0]]=
0,p=i=
1;i<n;i++
)
44 x[sa[i]]=cmp(y,sa[i-
1],sa[i],j)?p-
1:p++
;
45 }
46 }
47 void Height(
int n)
48 {
49 int i,j,k;
50 for(i=
1;i<=n;i++
)
51 rk[sa[i]]=
i;
52 for(i=k=
0;i<n;height[rk[i++]]=
k)
53 for(k?k--:
0,j=sa[rk[i]-
1];s[i+k]==s[j+k];k++
);
54 }
55 int Make()
56 {
57 int i,j,len;
58 strcpy(s,t);
59 len=
strlen(s);
60 s[len]=
'#';
61 s[len+
1]=
0;
62 for(i=
0,j=len-
1;i<=j;i++,j--
)
63 swap(t[i],t[j]);
64 strcat(s,t);
65 return len<<
1|
1;
66 }
67 void ST(
int n)
68 {
69 int i,j,p,q;
70 for(i=
1;i<=n;i++
)
71 st[i][
0]=
i;
72 for(j=
1;(
1<<j)<=n;j++
)
73 {
74 for(i=
1;i+(
1<<j)<=n;i++
)
75 {
76 p=st[i][j-
1];
77 q=st[i+(
1<<(j-
1))][j-
1];
78 st[i][j]=height[p]>height[q]?
q:p;
79 }
80 }
81 }
82 int RMQ(
int i,
int j)
83 {
84 int k;
85 if(i>
j)
86 swap(i,j);
87 i++
;
88 for(k=
0;(
1<<k)<=j-i+
1;k++
);
89 k--
;
90 i=
st[i][k];
91 j=st[j-(
1<<k)+
1][k];
92 return min(height[i],height[j]);
93 }
94 int main()
95 {
96 int len,i,j,st,ans,mid;
97 while(~scanf(
" %s",t))
98 {
99 len=
Make();
100 SA(len+
1,
200);
101 Height(len);
102 ST(len);
103 mid=len>>
1;
104 for(i=ans=st=
0;i<mid;i++
)
105 {
106 j=RMQ(rk[i],rk[len-i-
1]);
107 if((j<<
1)-
1>
ans)
108 {
109 ans=(j<<
1)-
1;
110 st=i-j+
1;
111 }
112 if(i)
113 {
114 j=RMQ(rk[i],rk[len-
i]);
115 if(j<<
1>
ans)
116 {
117 ans=j<<
1;
118 st=i-
j;
119 }
120 }
121 }
122 for(i=st;i<st+ans;i++
)
123 putchar(s[i]);
124 putchar(
'\n');
125 }
126 return 0;
127 }
转载于:https://www.cnblogs.com/DrunBee/archive/2012/07/05/2578452.html
相关资源：数据结构—成绩单生成器
