PALINY - Palindrome dài nhất
Tác giả: ll931110
Ngôn ngữ: Pascal
program PALINY;
uses math;
const
input = '';
output = '';
maxn = 50000;
var
a: array[0..maxn] of char;
rad: array[0..maxn] of longint;
res,n: longint;
procedure init;
var
f: text;
i: longint;
begin
assign(f, input);
reset(f);
readln(f, n);
for i := 0 to n - 1 do read(f, a[i]);
close(f);
end;
procedure solve;
var
i,j,k: longint;
begin
res := 0;
i := 0;
j := 0;
while i < n do
begin
while (i >= j) and (i + 1 + j < n) and (a[i - j] = a[i + 1 + j]) do inc(j);
rad[i] := j;
k := 1;
while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
begin
rad[i + k] := min(rad[i - k],rad[i] - k);
inc(k);
end;
j := max(j - k,0);
i := i + k;
end;
for i := 0 to n - 1 do if res < rad[i] * 2 then res := rad[i] * 2;
i := 0;
j := 0;
while i < n do
begin
while (i >= j) and (i + 2 + j < n) and (a[i - j] = a[i + 2 + j]) do inc(j);
rad[i] := j;
k := 1;
while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
begin
rad[i + k] := min(rad[i - k],rad[i] - k);
inc(k);
end;
j := max(j - k,0);
i := i + k;
end;
for i := 0 to n - 1 do if res < rad[i] * 2 + 1 then res := rad[i] * 2 + 1;
end;
procedure printresult;
var
f: text;
begin
assign(f, output);
rewrite(f);
writeln(f, res);
close(f);
end;
begin
init;
solve;
printresult;
end.