Bài giải NKPALIN spoj – 2118. Chuỗi đối xứng

Nguồn đề bài: http://vn.spoj.com/problems/NKPALIN/

1. Đề bài NKPALIN spoj

Một chuỗi được gọi là đối xứng (palindrome) nếu như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.

Yêu cầu: tìm một chuỗi con đối xứng dài nhất của một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi một số ký tự từ chuỗi ban đầu.

Dữ liệu vào

Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.

Kết qủa

Gồm một dòng duy nhất là một xâu con đối xứng dài nhất của xâu s. Nếu có nhiều kết quả, chỉ cần in ra một kết quả bất kỳ.

Giới hạn

Chuỗi s có độ dài không vượt quá 2000.

Ví dụ

input
lmevxeyzl

output

level

2. Hướng dẫn NKPALIN spoj

gọi F[i,j] là độ dài xâu đối xứng dài nhất thu được trong xâu S[1..i] và S[j..n] (i=1..n; j=n..1) n là độ dài xâu S,

Nghiệm bài toán F[n,1]

3. Code tham khảo NKPALIN spoj

[sociallocker]

program bt;
uses    math;
const   fi='';
        nmax=2000;
var
        f:text;
        S:ansistring;
        L:array[0..nmax+1,0..nmax+1] of word;
        n:word;

procedure docfile;
begin
        assign(f,fi); reset(f);
        readln(f,s);
        close(f);
end;

procedure bpa;
var     i,j:word;
        kq:ansistring;
begin
        n:=length(s);
        for i:=0 to n do
                begin
                        L[i,n+1]:=0;
                        L[0,i]:=0;
                end;
        for i:=1 to n do
                for j:=n downto 1 do
                        if s[i]=s[j] then
                                L[i,j]:=L[i-1,j+1] + 1
                        else
                                L[i,j]:=max(L[i-1,j],L[i,j+1]);
        i:=n; j:=1;
        kq:='';
        while (i>0) and (j<n+1) do
                if s[i]=s[j] then
                        begin
                                kq:=kq+s[i];
                                dec(i); inc(j);
                        end
                else
                        if l[i,j]=l[i-1,j] then
                                dec(i)
                        else
                                inc(j);
        writeln(kq);
end;

begin
        docfile;
        bpa;
end.

[/sociallocker]