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.
