NKPALIN - Chuỗi đối xứng

Tác giả: RR

Ngôn ngữ: Pascal

uses math;
const
  MAXN          =       2011;

var
  s             :       ansistring;
  n             :       longint;
  f             :       array[1..MAXN,1..MAXN] of longint;

procedure init;
    var
      k,i,j:longint;
    begin
      for i:=1 to n do f[i,i]:=1;

      for k:=1 to n-1 do
      for i:=1 to n-k do
        begin
          j:=i+k;
          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;
    end;

procedure solve(l,r:longint);
    begin
      if l>r then exit;
      if s[l]=s[r] then
        begin
          write(s[l]);
          solve(l+1,r-1);
          if l<>r then write(s[r]);
        end
      else
        if f[l+1,r]>f[l,r-1] then solve(l+1,r)
        else solve(l,r-1);
    end;

begin
  readln(s); n:=length(s);
  init;
  solve(1,n);
end.

Download