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...
Nội dung trích xuất từ tài liệu:
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ấtCho hai xâu X =x1x2…xm và Y=y1y2…yn. Tìm xâu Z = z1z2…zk là xâu con chung dàinhấ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 ánTa 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ủaY).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ồiDễ 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ếtNhư vậy B[n,m] cho biết độ dài của xâu con chung dài nhất. Để chi ra tường minhxâ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ữ PascalVAR 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.outint main(){char *s1=new char[10000],*s2=new char[10000];//Đọc fileifstream fi(Input);fi>>s1;fi.get();fi>>s2;fi.close();int m=strlen(s1),n=strlen(s2);//Tạo động mảng 2 chiềuint **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