Xâu con chung dài nhất

Phương pháp quy hoạch động giải bài toán xâu con chung dài nhất:

1. Bài toán:

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.

Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

Input

Dòng 1: chứa xâu A

Dòng 2: chứa xâu B

Output

Chỉ gồm một dòng ghi độ dài xâu C tìm được

Example

Input:

abc1def2ghi3

abcdefghi123

Output:

10

Link: http://vn.spoj.pl/problems/QBSTR/

2. Tiếp cận bài toán:

Định nghĩa xâu con của một xâu: một xâu X có dộ dài l là xâu con của xâu Y có độ dài m khi có một dãy c sao cho 1<=c[1]<=c[2]<=c[3]<…<=c[i]<=…c[l]<=m, và X[c[i]]=Y[c[i]], mọi 1<=i<=l. Nói một cách khác, từ xâu gốc ta xóa đi các kí tự tại các vị trí tùy ý, các kí tự còn lại được dồn lại kề nhau và vẫn bảo toàn thứ tự.

Ví dụ: Có xâu X: abcdfr. Các xâu con có thể là a, ab,  bc, bd, dfr, abcdfr,…Các xâu không phải xâu con là ba,cda,…

Để giải quyết bài toán này đầu tiên, ta xét bài toán đơn giản hơn.

Bài toán 1: Có 2 xâu, một xâu có m kí tự, xâu còn lại không có kí tự nào. Với bài toán này dễ thấy độ dài xâu con chung dài nhất là 0 (không có xâu nào).

Bài toán 2: Có hai xâu, mỗi xâu có đúng một kí tự.

Ví dụ 2.1: xâu X: a, xâu Y: b. Dễ thấy độ dài xâu con chung dài nhất là 0, vì không có xâu nào thỏa mãn.

Ví dụ 2.2: xâu X: a, xâu Y: a. Dễ thấy độ dài xâu con chung dài nhất là 1, xâu con chung khi đó là xâu có một kí tự a.

Bài toán 3: Có hai xâu, xâu X là: abc1def2ghi3, xâu Y là: abcdefghi123. Làm thế nào để có đáp án.

Ta giả sữ đã biết cấu trả lời trong trường hợp xâu X có độ dài i-1 kí tự đầu tiên, xâu Y có độ dài j-1 kí tự đầu tiên, khi đó đáp án trong trường hợp xâu X có độ dài i kí tự đầu tiên, xâu Y có độ dài j kí tự

đầu tiên thì sao? F[i-1][j-1],f[i-1][j],f[i][j-1] đã biết, F[i][j]=?.

Xâu X: x1x2…xi-1xi

Xâu Y: y1y2…yj-1yj

Ta có các trương hợp sau:

TH1: xi=yj, như vậy thì f[i][j]=f[i-1][j-1]+1.

Th2: xi!=yj, f[i][j]=max(f[i-1][j],f[i][j-1]).

Các bạn vẽ bảng sau:

	1	2	3	4	j-1	j	7	8	9	10	11	12
1
2
3
4
5
i-1					F[i-1][j-1]	F[i-1][j]
i					F[i][j-1]	F[i][j]
8
9
10
11
12

Tính như thế nào? Trong bài này ta tính từng dòng, nghĩa là ta tính hết f[i-1][j], thì sau đó ta mới f[i][j], mọi j.

Trên một dòng muốn tính f[i][j] thì trước hết ta phải tính f[i][j-1].

3.Code:

/*Code được cài trên IDE DevC++*/

#include<iostream>

#include<algorithm>

#include<cstring>

#define maxS 1001

using namespace std;

char a[maxS],b[maxS];

int f[maxS][maxS];

int main(){

    // Doc du lieu

    scanf("%s",&a);

    scanf("%s",&b);

    // Khoi tao mang f

    memset(f,0,sizeof(f));

    int da=strlen(a);

    int db=strlen(b);

    int i,j;

    for(i=1;i<=da;++i)

    for(j=1;j<=db;++j)

        if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;

        else f[i][j]=max(f[i-1][j],f[i][j-1]);

    // Ket qua o f[da][db]

    printf("%d",f[da][db]);   

    return 0;   

}

4. Độ phức tap:

O(m*n) về xử lý.

O(m*n) không gian lưu trữ.

5. Ghi chú:

Code trên đã test trên vn.spoj.pl. Các bạn chú ý tài liệu trên mình biên soạn chỉ dành cho CLB thuật toán khoa CNTT đại học Nha Trang.

Tham khảo:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem