Bài toán tìm chuỗi con chung dài nhất
Cho hai xâu X =x
1
x
2
…x
m
và Y=y
1
y
2
…y
n
. Tìm xâu Z = z
1
z
2
…z
k
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 X
i
(phần đầu của X) và Y
j
(phần đầu của
Y).
Cơ sở

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;

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 "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);

{
B[i][j]=B[i][j-1];
T[i][j]=1;
}
}
ofstream fo(Output);
fo<<B[m][n]<<endl;

int len=B[m][n];
char *s=new char[len+1];
s[len]=0;

//Truy vết
while (m>=0 && n>=0)
{
if (T[m][n]==0)
{
s[ len]=s1[m-1];
m ;
n ;
}
else if (T[m][n]==-1)
m ;
else
n ;
}
fo<<s;
fo.close();

//Giải phóng các vùng nhớ cấp phát động