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.

Download