Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const maxn=2000;
var a,b,kq:array[0..maxn] of char;
    f:array[0..maxn,0..maxn] of integer;
    num:integer;

procedure rf;
begin
     num:=0;
     while not eoln do
     begin
          inc(num);
          read(a[num]);
     end;
end;
{---------------}
procedure pr;
var i,j:integer;
begin
     fillchar(f,sizeof(f),0);
     for i:=1 to num do
         b[i]:=a[num-i+1];
     for i:=1 to num do
          for j:=1 to num do
          begin
               if f[i-1,j]>=f[i,j-1] then f[i,j]:=f[i-1,j]
               else f[i,j]:=f[i,j-1];
               if (a[i]=b[j]) and (f[i,j]<=f[i-1,j-1]) then
                   f[i,j]:=f[i-1,j-1]+1;
          end;
end;
{---------------}
procedure wf;
var i,j,c,pre:integer;
begin
     repeat
           if a[i]=b[j] then
           begin
                write(a[i]);
                dec(i);
                dec(j);
           end
           else
           begin
                if f[i,j]=f[i-1,j] then dec(i)
                else dec(j);
           end;
     until (f[i,j]=0);
end;
{---------------}
begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define SZ 2005
#define FOR(i, a, b) for( int i = (a), _b = (b); i <= _b; ++i )
#define max(a, b) ((a) > (b) ? (a) : (b))
char s[SZ];
int f[SZ][SZ], n;

void solve() {
    FOR( len, 1, n ) FOR( i, 0, n-len ) {
        int j = i + len - 1;
        if ( len == 1 ) f[i][j] = 1;
        //else if ( len == 2 ) f[i][j] = s[i] == s[j] ? 2 : max(f[i][j], f[j][j]);
        else f[i][j] = s[i] == s[j] ? f[i+1][j-1] + 2 : max(f[i][j-1], f[i+1][j]);
        /*printf( "%d %d %d\n", len, i, j);
        FOR(i, 0, n-1) {
            FOR(j, 0, n-1) printf( "%3d", f[i][j] );
            putchar('\n');
        }*/
    }
}

void print() {
    char res[SZ]; memset(res, '\0', sizeof res);
    int i = 0, j = n-1, l = 0;
    while( i <= j ) {
        if ( f[i][j] == f[i+1][j] ) ++i;
        else if ( f[i][j] == f[i][j-1] ) --j;
        else {
            res[l++] = s[i];
            ++i; --j;
        }
    }
    printf( "%s", res );
    if( f[0][n-1] % 2 ) res[--l] = 0;
    reverse(res, res+l);
    puts(res);
}

int main() {
    scanf( "%s", s ); n = strlen(s);
    solve();
    print();
    return 0;
}

Code mẫu của ladpro98

program nkpalin;//qhd
uses    math;
const   fi='';
var     s,res:ansistring;
        f:array[1..2000,1..2000] of longint;
        check:array[1..2000,1..2000] of boolean;
        maxL,dau,cuoi,i,j,kq,len:longint;
procedure input;
var     inp:text;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,s);
        close(inp);
end;

function qhd(i,j:longint):longint;
begin
        if (check[i,j]) or (i>j) then exit(f[i,j]);
        check[i,j]:=true;
        if s[i]=s[j] then
        begin
                f[i,j]:=qhd(i+1,j-1)+2;
                exit(f[i,j]);
        end;
        f[i,j]:=max(qhd(i+1,j),qhd(i,j-1));

        exit(f[i,j]);

end;

procedure init;
var     i:longint;
begin
        for i:=1 to length(S) do
        begin
                check[i,i]:=true;
                f[i,i]:=1;
        end;
end;

begin
        input;
        init;
        for i:=1 to length(s) do for j:=1 to length(s) do qhd(i,j);
        kq:=qhd(1,length(s));
        len:=high(longint);
        for i:=1 to length(s) do
        for j:=i to length(s) do
        begin
                if (f[i,j]=kq) and ((j-i+1)<len) then
                begin
                        dau:=i;
                        cuoi:=j;
                        len:=j-i+1;
                end;
        end;
        i:=dau;
        j:=cuoi;
        res:='';
        while (kq>1) do
        begin

                if s[i]=s[j] then
                begin
                        res:=res+s[i];
                        dec(kq,2);
                        inc(i);
                        dec(j);
                end
                else if f[i+1,j]<f[i,j-1] then
                begin
                        dec(j);
                end
                else inc(i);
        end;
        if kq=1 then
        begin
                res:=res+s[i];
                for i:=length(res)-1 downto 1 do
                res:=res+res[i];
        end
        else
        begin
                for i:=length(res) downto 1 do
                res:=res+res[i];
        end;
        write(res);


end.

Code mẫu của RR

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.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <string.h>

main()
{
      char s[2000],B[2000]; int f[2000][2000],max[2000][2000],min[2000][2000];
      gets(s);
      int n=strlen(s)-1;
      f[0][0]=1;
      min[0][0]=0;
      max[0][0]=0;
      for(int i=1;i<=n;i++)
      {
           f[i][i]=1;
           f[i][i-1]=0;
           max[i][i]=i;
           min[i][i]=i;
      }
      for(int i=1;i<=n;i++)
          for(int j=0;j<=n-i;j++)
          {
               if(s[j]==s[j+i])
               { 
                    f[j][j+i]=f[j+1][j+i-1]+2;
                    max[j][j+i]=j+i;
                    min[j][j+i]=j;
               }    

               else
               {
                    if(f[j+1][j+i]>f[j][j+i-1])
                    {
                         f[j][j+i]=f[j+1][j+i];
                         max[j][j+i]=max[j+1][j+i];
                         min[j][j+i]=min[j+1][j+i];
                    }
                    else
                    {
                         f[j][j+i]=f[j][j+i-1];
                         max[j][j+i]=max[j][j+i-1];
                         min[j][j+i]=min[j][j+i-1];
                    }
               }

          }
      int x=0,y=n,z=f[0][n],t=f[0][n];
     // printf("%d %d %d\n",min[0][n],max[0][n],t);
      while(z!=0 && z!=1)
      {
          B[(t-z)/2+1]=s[min[x][y]];
          B[(t+z)/2]=s[max[x][y]];
          int xx=x;
          x=min[x][y]+1;
          y=max[xx][y]-1;
          z=z-2;
         // printf("%d %d\n",x,y);
      }
      if(z==1) 
          B[(t+1)/2]=s[min[x][y]];
      for(int i=1;i<=t;i++)
          printf("%c",B[i]);
     // getch();
}

Code mẫu của ll931110

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.

Code mẫu của skyvn97

#include<stdio.h>
#include<string.h>
#define MAX 2222
char s[MAX];
bool t[MAX];
int o[MAX][MAX];
int l;
int max(int x,int y)
{
    if (x>y) return (x);else return (y);
}
void count(int i,int j)
{
    if (i>j) return;
    if (o[i][j]!=0) return;
    if (i==j)
       {
        o[i][j]=1;
        return;
       }     
    if (s[i-1]==s[j-1])
       {
        if (j-i==1)
           {
            o[i][j]=2;
            return;
           }
        if (o[i+1][j-1]==0) count(i+1,j-1);
        o[i][j]=o[i+1][j-1]+2;
       }
    else
        {
         if (o[i+1][j]==0) count(i+1,j);
         if (o[i][j-1]==0) count(i,j-1);
         o[i][j]=max(o[i+1][j],o[i][j-1]);
        }
    return;
}
void init(void)
{
     int i;
     gets(s);
     l=strlen(s);
     for (i=1;i<=l;i=i+1) t[i]=false;
}
void optimize(void)
{
     int i,j;     
     for (i=1;i<l;i=i+1)
         for (j=i+1;j<=l;j=j+1) count(i,j);     
}
void trace(void)
{
     int i,j;
     i=1;j=l;
     while (i<=j)
           {
            if (s[i-1]==s[j-1])
               {
                t[i]=true;
                t[j]=true;
                i=i+1;
                j=j-1;
               }
            else
                {
                 if (o[i][j]==o[i+1][j]) i=i+1;
                 else j=j-1;                    
                }
           }     
     for (i=1;i<=l;i=i+1)
         if (t[i]) printf("%c",s[i-1]);
}
int main(void)
{
    init();
    optimize();
    trace();
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

char a[2020];
int f[2020][2020];
int n;

int calc(int i,int j) {
    if(i>j) return 0;
    if(i==j) return 1;
    int &ret = f[i][j];
    if(ret!=-1) return ret;
    ret = 0;
    ret >?= calc(i+1,j);
    ret >?= calc(i,j-1);
    if(a[i]==a[j]) ret >?= calc(i+1,j-1) + 2;
    return ret;
}

void truy(int i,int j) {
    if(i>j) return;
    if(i==j) {
        cout << a[i];
        return;
    }
    int r = f[i][j];
    if(r==calc(i+1,j)) { truy(i+1,j); return; }
    if(r==calc(i,j-1)) { truy(i,j-1); return; }
    if(a[i]==a[j] && r==calc(i+1,j-1)+2) { 
        cout << a[i];
        truy(i+1,j-1);
        cout << a[j];
        return;
    }
}

int main() {
    gets(a);
    n = strlen(a);
    memset( f, -1, sizeof(f));
    calc(0,n-1);
    truy(0,n-1);
    cout << endl;
    return 0;
}