NKPALIN - Chuỗi đối xứng
Tác giả: ll931110
Ngôn ngữ: Pascal
Program NKPALIN;
Const
input = '';
output = '';
Var
s: array[1..2000] of char;
F: array[0..2000,0..2000] of integer;
fo: text;
n: integer;
Procedure init;
Var
fi: text;
Begin
Assign(fi, input);
Reset(fi);
n:= 0;
While not eoln(fi) do
Begin
inc(n);
read(fi, s[n]);
End;
End;
Function max(p,q: integer): integer;
Begin
If p < q then max:= q else max:= p;
End;
Procedure optimize;
Var
i,j: integer;
Begin
Fillchar(F, sizeof(F), 0);
For i:= 1 to n do F[i,i]:= 1;
For i:= n downto 1 do
For j:= i + 1 to n do
If s[i] = s[j] then F[i,j]:= F[i + 1,j - 1] + 2
else F[i,j]:= max(F[i + 1,j], F[i,j - 1]);
End;
Procedure trace(x,y: integer);
Begin
If x = y then write(fo, s[x])
else if x < y then
Begin
If s[x] = s[y] then
Begin
write(fo, s[x]);
trace(x + 1,y - 1);
write(fo, s[x]);
End
else
if F[x + 1,y] > F[x,y - 1] then trace(x + 1,y)
else trace(x,y - 1);
End;
End;
Begin
init;
optimize;
Assign(fo, output);
Rewrite(fo);
trace(1,n);
Close(fo);
End.