02/10/2018, 13:55
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à ...
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 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]
