PALINY - Palindrome dài nhất
Tác giả: RR
Ngôn ngữ: Pascal
//Written by RR
{$MODE OBJFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 50111;
nkey = 2;
hkey : array[1..nkey] of longint=(
30011,30013);
var
f1,f2 : text;
n,res : longint;
a : array[1..MAXN] of longint;
lt : array[1..nkey,0..MAXN] of longint;
sum : array[1..nkey,0..1,0..MAXN] of longint;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
c:char;
begin
readln(f1,n);
for i:=1 to n do
begin
read(f1,c);
a[i]:=ord(c)-ord('a');
end;
end;
procedure init;
var
now,hashkey,i:longint;
begin
for now:=1 to nkey do
begin
hashkey:=hkey[now];
lt[now,0]:=1;
for i:=1 to n do
lt[now,i]:=(lt[now,i-1]*26) mod hashkey;
for i:=1 to n do
sum[now,0,i]:=(sum[now,0,i-1]+lt[now,i-1]*a[i]) mod hashkey;
for i:=n downto 1 do
sum[now,1,i]:=(sum[now,1,i+1]+lt[now,n-i]*a[i]) mod hashkey;
end;
end;
function check(val:longint):boolean;
var
i,j,l1,l2,now:longint;
ok:boolean;
begin
for i:=1 to n-val+1 do
begin
j:=i+val-1;
l1:=i-1; l2:=n-j;
if l1=l2 then begin l1:=0; l2:=0; end
else if l1>l2 then begin l2:=l1-l2; l1:=0; end
else begin l1:=l2-l1; l2:=0; end;
ok:=true;
for now:=1 to nkey do
if (lt[now,l1]*(sum[now,0,j]-sum[now,0,i-1]+hkey[now])) mod hkey[now]
<>(lt[now,l2]*(sum[now,1,i]-sum[now,1,j+1]+hkey[now])) mod hkey[now]
then ok:=false;
if ok then exit(true);
end;
exit(false);
end;
function chan:longint;
var
l,r,mid,res:longint;
begin
l:=1; r:=n shr 1; res:=0;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid shl 1) then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res shl 1);
end;
function le:longint;
var
l,r,mid,res:longint;
begin
l:=0; r:=n shr 1; res:=0;
while l<=r do
begin
mid:=(l+r) shr 1;
if check(mid shl 1+1) then
begin
res:=mid;
l:=mid+1;
end
else r:=mid-1;
end;
exit(res shl 1+1);
end;
begin
openF;
inp;
init;
writeln(f2,max(chan,le));
closeF;
end.