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

Chia sẻ: Abcdef_45 Abcdef_45 | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

1.265
lượt xem 82
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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[0..m, 0..n] 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...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài toán tìm chuỗi con chung dài nhất

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[0..m, 0..n] 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[i,j]=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à xiyj 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[1..m, 1..n] để 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[0..100,0..100] OF INTEGER; m,n,len:INTEGER; PROCEDURE GetInput; VAR f:TEXT; BEGIN assign(f,'xaucon.inp'); 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-1,j]>B[i,j-1] THEN BEGIN B[i,j]:=B[i-1,j]; T[i,j]:=1; END ELSE BEGIN B[i,j]:=B[i,j-1]; T[i,j]:=-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,'xaucon.out'); 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 #include #include using namespace std; #define Input "xaucon.inp" #define Output "xaucon.out" int main() {
char *s1=new char[10000],*s2=new char[10000]; //Đọc file ifstream fi(Input); fi>>s1; fi.get(); fi>>s2; fi.close(); int m=strlen(s1),n=strlen(s2); //Tạo động mảng 2 chiều int **B=new int*[m+1]; int **T=new int*[m+1]; for (int i=0; i
{ B[i][j]=B[i][j-1]; T[i][j]=1; } } ofstream fo(Output); fo