NỘI DUNG TRÌNH BÀY

Phát biểu bài toán

Giới thiệu phương pháp thực hiện

Phân tích bài toán

Giải pháp đệ quy

Áp dụng vào bước tạo bảng

Tạo bảng

Tổng hợp kết quả

Minh họa bằng ví dụ

Phân tích độ phức tạp thời gian, không gian
PHÁT BIỂU BÀI TOÁN
Xâu con cực đại:
S là xâu con của T nếu S nhận được bằng cách
xoá đi một số ký tự nào đó trong T.
Ví dụ: ‘EAC’ là xâu con của ‘CEAEEC’
Xâu con chung:
Nếu xóa một số ký tự của hai xâu thì hai xâu con
còn lại của chúng bằng nhau
Ví dụ: S1=‘ABCDAE’ và S2=‘XYACADK’ có xâu
‘ACD’ là xâu con chung có độ dài cực đại.
Bài toán đặt ra:

L(k, h) là bài toán xâu con chung cực đại, với
k ∈ N*: Độ dài dãy a
1
a
2
…a
k
( k ≤ m )
h ∈ N*: Độ dài dãy b
1
b
2
…b
h
(h ≤ n)
 Bài toán ban đầu là L(m, n)

Các giá trị cần tìm:
LCS [k,h]: độ dài cực đại của xâu con chung của
L(k, h)
s: xâu con chung của bài toán L(k, h)
GIẢI PHÁP ĐỆ QUY

Trường hợp đơn giản nhất
Nếu (i=0) hoặc (j=0) thì L(i,j)=0

Nếu (i>0) and (j>0) and(a
i
<> b
j


Nếu a
i
<>b
j
, lúc này cho S
1
là LCS của A
i-1
và B
j
, và S
2

là LCS của A
i
và B
j-1
. S sẽ là giá trị lớn hơn
trong 2 giá trị S
1
và S
2
.
TẠO BẢNG

Cho L[i, j] = LCS[i, j], lúc này
 L[i, j] sẽ phụ thuộc vào 3 giá trị sau

Phần tử L[i-1, j]


Nếu a
i
= b
j
thì đặt a
i
hoặc b
j
vào bên trái dãy
S (ở đầu xâu)

Nếu a
i
<> b
j
thì

lùi về L[i - 1, j] trong trường hợp L[i - 1, j] > L[i, j – 1]

ngược lại, lùi về L[i, j – 1] trong trường hợp L[i - 1, j]
≤ L[i, j – 1]
Ví dụ

File đầu vào: gồm 2 xâu:

S1: CARROT

S2: PARTY


L : Mang;
s1, s2, s3 : String;
m, n, i, j : Byte;
f: text;
THỦ TỤC LapBang
Procedure LapBang;
Var
i,j: Byte;
Begin
FillChar(L, SizeOf(L), 0);
For i:=1 to m do
For j:=1 to n do
if s1[i] = s2[j] then
L[i,j]:= 1 + L[i-1,j-1]
else
L[i,j]:= max (L[i,j-1] , L[i-1,j]);
End;
THỦ TỤC X auConLonNhat
Procedure XauConLonNhat;
Var
i,j :byte;
Begin
s3[0]:=chr(L[m, n]);
i:=m;
j:=n;
Repeat
if s1[i]=s2[j] then
Begin
Insert(s1[i], s3, 1);
dec(i);

O 5
0 0 0 0 0 0
T 6
0 0 0 0 0 0
S1(i)
S2(j)
Max (L[i, j-1,
L[i -1, j])
0 0 0 0 0
0
1 + L[i-1, j-1]
If s1[i] <> s2[j]
If s1[i] = s2[j]
1 1 1 1
0 1 2 2 2
0 1 2 2 2
0 1 2 2 2
0 1 2 3 3
If L[i, j] = L[i-1, j]
then dec(i)
If L[i, j] <> L[i-1, j] then dec(j)
3
S3 = “”S3 = 3
2
3
S3 = 3T
1
D ng vì i = 0ừ
S3 = 3RTS3 = 3ART
If s1[i] = s2[j] then dec(i); dec(j)

for j:=1 to n do Write(f, s2[j]:7); Writeln(f);
for i:=1 to m do
begin
Write(f, s1[i]:3);
write(f, L[i, 1]:4);
for j:=2 to n do
Write(f, L[i, j]:7);
writeln(f);
end;
Close(f)
End;
CHƯƠNG TRÌNH CHÍNH
Begin
DocDuLieu;
LapBang;
XauConLonNhat;
InKetQua;
End.
PHÂN TÍCH ĐỘ PHỨC TẠP

Điền vào bảng L[0 m, 0 n] mất O(m.n) thời gian, đây cũng là thời
gian chạy của thủ tục Tạo bảng

Không gian được yêu cầu là O(m.n)
XIN CẢM ƠN !!!