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

Cho hai xâu X =x₁x₂…x_m và Y=y₁y₂…y_n. Tìm xâu Z = z₁z₂…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 á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 X_i (phần đầu của X) và Y_j (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ồiDễ dàng có các nhận xét sau:
- Nếu i,j > 0 và x_i=y_i thì B[i,j] = B[i-1,j-1] + 1- Nếu i,j > 0 và x_i<>y_j 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 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 <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);

  //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<=m; i++)
  {
    B[i]=new int[n+1];
      T[i]=new int[n+1];
  }

  //Khởi gán bảng phương án
  for (int i=0; i<=n; i++) B[0][i]=0;
  for (int i=0; i<=m; i++) B[i][0]=0;

  //Tính bảng phương án và bảng truy vết
  for (int i=1; i<=m; i++)
    for (int j=1; j<=n; j++)
      if (s1[i-1]==s2[j-1])
      {
        B[i][j]=B[i-1][j-1]+1;
        T[i][j]=0;
      }
      else
      {
        if (B[i-1][j]>B[i][j-1])
        {
          B[i][j]=B[i-1][j];
          T[i][j]=-1;
        }
        else
        {
          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
  for (int i=0; i<n; i++)
  {
    delete []B[i];
      delete []T[i];
  }
  delete []B;
  delete []T;

}