02/10/2018, 13:58
QBSTR spoj – Xâu con chung dài nhất
Nguồn đề bài http://vn.spoj.com/problems/QBSTR/ 1. Đề bài QBSTR spoj Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X. Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B. ...
Nguồn đề bài http://vn.spoj.com/problems/QBSTR/
1. Đề bài QBSTR spoj
Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.
Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.
Input
Dòng 1: chứa xâu A
Dòng 2: chứa xâu B
Output
Chỉ gồm một dòng ghi độ dài xâu C tìm được
Example
Input:
abc1def2ghi3
abcdefghi123
Output:
10
2. Hướng dẫn QBSTR spoj
bài này phải sử dụng QHĐ.
+ Gọi F[i,j] là độ dài xâu con chung dài nhất tìm được khi xét i kí tự đầu tiên trong A và j kí tự đầu tiên trong B.
+ Nếu A[i]=B[j] thì F[i,j]:=F[i-1,j-1]+1.
+ ngược lại F[i,j]:=max(F[i-1,j],F[i,j-1]).
3. code tham khảo QBSTR spoj
program qbstr;
uses math;
const fi=';
nmax=1000;
var
f:text;
s1,s2:ansistring;
KQ:array[0..nmax+10,0..nmax+10] of word;
procedure docfile;
begin
assign(f,fi); reset(f);
readln(f,s1);
readln(f,s2);
close(f);
end;
procedure bpa;
var i,j:word;
begin
for i:=0 to length(s1) do
kq[i,0]:=0;
for i:=0 to length(s2) do
kq[0,i]:=0;
for i:=1 to length(s1) do
for j:=1 to length(s2) do
if s1[i]=s2[j] then
KQ[i,j]:=kq[i-1,j-1] + 1
else
KQ[i,j]:=max(kq[i,j-1],kq[i-1,j]);
writeln(kq[length(s1),length(s2)]);
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 | program qbstr; uses math; const fi='; nmax=1000; var f:text; s1,s2:ansistring; KQ:array[0..nmax+10,0..nmax+10] of word; procedure docfile; begin assign(f,fi); reset(f); readln(f,s1); readln(f,s2); close(f); end; procedure bpa; var i,j:word; begin for i:=0 to length(s1) do kq[i,0]:=0; for i:=0 to length(s2) do kq[0,i]:=0; for i:=1 to length(s1) do for j:=1 to length(s2) do if s1[i]=s2[j] then KQ[i,j]:=kq[i-1,j-1] + 1 else KQ[i,j]:=max(kq[i,j-1],kq[i-1,j]); writeln(kq[length(s1),length(s2)]); end; begin docfile; bpa; end. |
