PTIT014C - 2014 Bài C - Xâu con chung dài nhất

Link Sub: http://www.spoj.com/PTIT/problems/PTIT014C/
Người Gửi: Dương Lee

• Problem:

Xâu ký tự S được gọi là xâu con của xâu ký tự T nếu ta có thể xoá đi một số ký tự trong xâu T để nhận được xâu S. Gọi LCS(X, Y) là độ dài xâu con chung dài nhất của X và Y.  
Yêu cầu: Cho n xâu S_1, S_2, ... ,S_n. Hãy tính G = max{ LCS(S_i, S_j) } với tất cả các chỉ số i khác j thỏa mãn 1 <= i, j <= n.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa số nguyên K là số bộ dữ liệu. Tiếp theo là K (K≤100) dòng, mỗi dòng là một bộ dữ liệu có cấu trúc như sau:  
- Dòng đầu tiên của nhóm chứa số nguyên.  
- Dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài không vượt quá 30, chỉ gồm các ký tự in hoa.

Output

Với mỗi bộ dữ liệu ghi ra trên một dòng, mỗi dòng ghi ra một số nguyên  là câu trả lời tương ứng với bộ dữ liệu trong dữ liệu vào.

Example:

Input

2
2
ALICE
BOB
2
ABCB
BCAB

Output:

0
3

• Solution:

- Bài này không thấy cho n nên mình coi 1<=n<=1000.
- Áp dụng quy hoạch động cho xâu con chung dài nhất
Tư tưởng:
- F[i][j] là xâu con chung max của xâu S1(0->i-1) và S2(0->j-1)
- Nếu S1[i]==S2[j] thì F[i+1][j+1]=F[i][j]+1;
- Ngược lại thì F[i+1][j+1] nhận giá trị max của F[i+1][j] và F[i][j+1] là xâu con chung lớn nhất của S1(0->i), S2(0->j-1) hoặc S1(0->i-1), S2(0->j).
Xem hình để hiểu rõ hơn về LCS:

LCS - Longest Common Subsequence - Dãy con chung dài nhất

• Code:

C++:

https://ideone.com/JmO28p

#include <iostream>
#include <math.h>
using namespace std;

int n;
string S[1003];
void read()
{
    cin>>n;
    for (int i=1; i<=n; i++)
        cin>>S[i];
}

int F[31][31];
void init()
{
    for (int i=0; i<=30; i++)
        for (int j=0; j<=30; j++)
            F[i][j]=0;
}

int LCS(string S1, string S2)
{
    init();
    
    for (int i=0; i<S1.length(); i++)
    {
        for (int j=0; j<S2.length(); j++)
        {
            if (S1[i]==S2[j])
                F[i+1][j+1]=F[i][j]+1;
            else
                F[i+1][j+1]=max(F[i][j+1], F[i+1][j]);
        }
    }
    return F[S1.length()][S2.length()];
}

int main ()
{
    int t;
    cin>>t;
    while (1)
    {
        if (t==0) break;
        t--;
        read();
        int maxLCS = 0;
        for (int i=1; i<=n; i++)
        {
            for (int j=i+1; j<=n; j++)
                maxLCS = max(maxLCS, LCS(S[i], S[j]));
        }
        cout<<maxLCS<<endl;
    }
    return 0;
}

JAVA:

...

Python:

...

Author : DL

Share this

Related Posts