题意：求一个字符串的最长回文子串
n<=1000
思路：这是一道论文题
需要注意的细节：
1.奇偶分类
2.中间的分割符与最后的附加字母都是最小值，但两者不能相同，否则height可能会出现问题
答案即为min(height[rank[x]+1]...height[rank[y]])
1 var f:array[0..3000,0..11]of longint; 2 x,y,sa,rank,height,a,wc,wd:array[0..3000]of longint; 3 ch:ansistring; 4 n,m,i,k,max,tmp,t,j:longint; 5 6 function min(x,y:longint):longint; 7 begin 8 if x<y then exit(x); 9 exit(y); 10 end; 11 12 procedure swap(var x,y:longint); 13 var t:longint; 14 begin 15 t:=x; x:=y; y:=t; 16 end; 17 18 function cmp(a,b,l:longint):boolean; 19 begin 20 exit((y[a]=y[b])and(y[a+l]=y[b+l])); 21 end; 22 23 procedure getsa(n:longint); 24 var i,j,p:longint; 25 begin 26 for i:=0 to n-1 do 27 begin 28 x[i]:=a[i]; 29 inc(wc[a[i]]); 30 end; 31 for i:=1 to m-1 do wc[i]:=wc[i-1]+wc[i]; 32 for i:=n-1 downto 0 do 33 begin 34 dec(wc[x[i]]); 35 sa[wc[x[i]]]:=i; 36 end; 37 j:=1; p:=1; 38 while p<n do 39 begin 40 p:=0; 41 for i:=n-j to n-1 do 42 begin 43 y[p]:=i; inc(p); 44 end; 45 for i:=0 to n-1 do 46 if sa[i]>=j then begin y[p]:=sa[i]-j; inc(p); end; 47 for i:=0 to n-1 do wd[i]:=x[y[i]]; 48 for i:=0 to m-1 do wc[i]:=0; 49 for i:=0 to n-1 do inc(wc[wd[i]]); 50 for i:=1 to m-1 do wc[i]:=wc[i-1]+wc[i]; 51 for i:=n-1 downto 0 do 52 begin 53 dec(wc[wd[i]]); 54 sa[wc[wd[i]]]:=y[i]; 55 end; 56 for i:=0 to n do swap(x[i],y[i]); 57 p:=1; x[sa[0]]:=0; 58 for i:=1 to n-1 do 59 if cmp(sa[i-1],sa[i],j) then x[sa[i]]:=p-1 60 else begin x[sa[i]]:=p; inc(p); end; 61 j:=j*2; 62 m:=p; 63 end; 64 end; 65 66 procedure getheight(n:longint); 67 var i,j,k:longint; 68 begin 69 k:=0; 70 for i:=1 to n do rank[sa[i]]:=i; 71 for i:=0 to n-1 do 72 begin 73 if k>0 then dec(k); 74 j:=sa[rank[i]-1]; 75 while a[i+k]=a[j+k] do inc(k); 76 height[rank[i]]:=k; 77 end; 78 end; 79 80 function query(x,y:longint):longint; 81 var len,l:longint; 82 begin 83 len:=y-x+1; l:=trunc(ln(len)/ln(2)); 84 exit(min(f[x,l],f[y-(1<<l)+1,l])); 85 end; 86 87 function lcp(x,y:longint):longint; 88 var i,j:longint; 89 begin 90 //inc(x); inc(y); 91 i:=rank[x]; j:=rank[y]; 92 if i>j then swap(i,j); 93 inc(i); 94 exit(query(i,j)); 95 end; 96 97 procedure init; 98 begin 99 fillchar(a,sizeof(a),0); 100 fillchar(height,sizeof(height),0); 101 fillchar(sa,sizeof(sa),0); 102 fillchar(rank,sizeof(rank),0); 103 fillchar(f,sizeof(f),0); 104 fillchar(x,sizeof(x),0); 105 fillchar(y,sizeof(y),0); 106 fillchar(wc,sizeof(wc),0); 107 fillchar(wd,sizeof(wd),0); 108 end; 109 110 begin 111 assign(input,'ural1297.in'); reset(input); 112 assign(output,'ural1297.out'); rewrite(output); 113 while not eof do 114 begin 115 init; 116 readln(ch); 117 n:=length(ch); 118 if n=0 then break; 119 for i:=0 to n-1 do a[i]:=ord(ch[i+1]); 120 a[n]:=1; m:=300; 121 for i:=n+1 to 2*n do a[i]:=ord(ch[n-(i-n)+1]); 122 a[n*2+1]:=0; 123 getsa(n*2+2); 124 getheight(n*2+1); 125 m:=n*2+2; 126 t:=trunc(ln(m)/ln(2)); 127 for i:=2 to m do f[i,0]:=height[i]; 128 for i:=1 to t do 129 for j:=2 to m do 130 if j+(1<<(i-1))<=m then f[j,i]:=min(f[j,i-1],f[j+(1<<(i-1)),i-1]); 131 max:=0; k:=0; 132 for i:=0 to n-1 do 133 begin 134 tmp:=lcp(i,2*n-i)*2-1; 135 if tmp>max then 136 begin 137 max:=tmp; 138 k:=i; 139 end; 140 if i>0 then 141 begin 142 tmp:=lcp(i,n*2-i+1)*2; 143 if tmp>max then 144 begin 145 max:=tmp; 146 k:=i; 147 end; 148 end; 149 end; 150 if max mod 2=1 then 151 for j:=k-max div 2+1 to k+max div 2+1 do write(ch[j]) 152 else 153 for j:=k-max div 2+1 to k+max div 2 do write(ch[j]); 154 writeln; 155 // for i:=2 to n*2+2 do writeln(height[i]); 156 // for i:=1 to n*2+2 do writeln(rank[i]); 157 // writeln; 158 end; 159 160 161 162 close(input); 163 close(output); 164 end.