tailieunhanh - Bài toán tìm chuỗi con chung dài nhất

Cho hai xâu X =x1x2 xm và Y=y1y2 yn. Tìm xâu Z = z1z2 zk là xâu con chung dài nhất của X và Y. Một xâu con của xâu A là một cách chọn trong A một số phần tử giữ nguyên thứ tự. Bảng phương án Ta sẽ dùng mảng hai chiều B[0m, 0n] làm bảng phương án, trong đó B[i,j] là độ dài xâu chung dài nhất của các xâu con Xi (phần đầu của X) và Yj (phần đầu của Y). Cơ sở Rõ ràng nếu ít nhất một trong hai xâu X hoặc Y là xâu rỗng. | Bài toán tìm chuỗi con chung dài nhất Cho hai xâu X X1X2. xm và Y yiy2---yn. Tìm xâu Z là xâu con chung dài nhất của X và Y. Một xâu con của xâu A là một cách chọn trong A một số phần tử giữ nguyên thứ tự. Bảng phương án Ta sẽ dùng mảng hai chiều B làm bảng phương án trong đó B i j là độ dài xâu chung dài nhất của các xâu con Xi phần đầu của X và Yj phần đầu của Y . Cơ sở Rõ ràng nếu ít nhất một trong hai xâu X hoặc Y là xâu rỗng j 0 hoặc i 0 thì B ij 0. Công thức truy hồi Dễ dàng có các nhận xét sau - Nếu i j 0 và xi yi thì B i j B i-1 j-1 1 - Nếu i j 0 và xi yj thì B i j max B i j-1 B i-1 j Truy vết Như vậy B n m cho biết độ dài của xâu con chung dài nhất. Để chi ra tường minh xâu con chung dài nhất ta cần xây dựng bảng T để ghi nhận truy vết đánh dấu B i j được tính từ B i-1 j-1 hay B i j-1 hay B i-1 j . Cài đặt bài toán bằng ngôn ngữ Pascal VAR s1 s2 s STRING B T ARRAY of INTEGER m n len INTEGER PROCEDURE GetInput VAR f TEXT BEGIN assign f reset f readln f s1 readln f s2 close f m length s1 n length s2 END PROCEDURE Optimize VAR i j INTEGER begiN FOR i 0 TO m DO B i 0 0 FOR j 0 TO n DO B 0 j 0 FOR i 1 TO m DO FOR j 1 TO n DO IF s1 i s2 j THEN BEGIN B i j B i-1 j-1 1 T i j 0 END ELSE IF B i-1j B ij-1 THEN begin B i j B i-1 j T ij 1 END ELSE BEGIN B i j B i j-1 T ij -1 END END PROCEDURE Trace BEGIN len B m n s While m 0 AND n 0 DO BEGIN IF T m n 0 THEN BEGIN s s1 m s m m-1 n n-1 END ELSE IF T m n 1 THEN m m-1 ELSE n n-1 END END PROCEDURE PutOutput VAR f TEXT i INTEGER BEGIN assign f rewrite f writeln f len write f s close f END BEGIN GetInput Optimize Trace PutOutput END. Cài đặt bài toán bằng ngôn ngữ C include iostream include fstream include string. h using namespace std define Input define Output int main