Bài toán Số chung lớn nhất

Bài toán – Số chung lớn nhất

Cho 2 xâu:

     X = x₁x₂..xM. (Với xi là các kí tự số từ ‘0’ đến ‘9’)

     Y = y₁y₂..yN.( Với yi là các kí tự số từ ‘0’ đến ‘9’)

(M, N <= 250)

Ta gọi: Z = z₁z₂..zk là xâu chung của 2 xâu X, Y nếu xâu Z nhận đ­ợc từ xâu X bằng cách xoá đi một số kí tự và cũng nhận được từ xâu Y bằng cách xoá đi một số kí tự.

Yêu cầu: Tìm một xâu chung của 2 xâu X, Y sao cho xâu nhận được tạo thành một số lớn nhất có thể được.

Dữ liệu vào file: String.inp

Gồm 2 dòng, dòng 1 là xâu X, dòng 2 là xâu Y.

Kết quả ra file: String.out

Gồm 1 dòng duy nhất là số lớn nhất có thể nhận được.

Ví dụ:

Thuật toán

Để giải bài toán này, ta có thể sử dụng kỹ thuật động programming (DP).

Gọi f[i][j] là độ dài của xâu chung lớn nhất của hai xâu con X[1..i] và Y[1..j]. Ta có thể tính được f[i][j] bằng cách xét hai trường hợp:

• Nếu X[i] = Y[j], tức là ký tự cuối cùng của X và Y là giống nhau, ta có thể thêm ký tự đó vào xâu chung, và tính độ dài xâu chung của hai xâu con X[1..i-1] và Y[1..j-1] bằng cách lấy giá trị f[i-1][j-1] và cộng thêm 1.

• Nếu X[i] != Y[j], ta phải quyết định bỏ đi ký tự cuối cùng của X hoặc Y, để có được xâu chung lớn nhất. Ta có thể tính độ dài xâu chung của hai xâu con X[1..i-1] và Y[1..j] bằng cách lấy giá trị f[i-1][j], hoặc tính độ dài xâu chung của hai xâu con X[1..i] và Y[1..j-1] bằng cách lấy giá trị f[i][j-1]. Xâu chung lớn nhất của hai xâu con này sẽ là kết quả.

Cuối cùng, đáp án của bài toán là f[M][N].

Độ phức tạp của thuật toán này là O(MN), vì ta cần tính giá trị của mọi f[i][j]. Vì M và N không quá lớn, nên thuật toán này có thể chạy trong thời gian chấp nhận được.

Cài đặt bài toán với Python

def solve(X, Y):
    n = len(X)
    m = len(Y)

    f = [[0] * (m+1) for _ in range(n+1)]

    for i in range(1, n+1):
        for j in range(1, m+1):
            if X[i-1] == Y[j-1]:
                f[i][j] = f[i-1][j-1] + 1
            else:
                f[i][j] = max(f[i-1][j], f[i][j-1])

    return f[n][m]


with open("String.inp", "r") as f:
    X = f.readline().strip()
    Y = f.readline().strip()

result = solve(X, Y)

with open("String.out", "w") as f:
    f.write(str(result))

Cài đặt bài toán với C++

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

int solve(string X, string Y) {
    int n = X.length();
    int m = Y.length();

    int f[n+1][m+1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                f[i][j] = 0;
            } else if (X[i-1] == Y[j-1]) {
                f[i][j] = f[i-1][j-1] + 1;
            } else {
                f[i][j] = max(f[i-1][j], f[i][j-1]);
            }
        }
    }

    return f[n][m];
}

int main() {
    string X, Y;
    ifstream fin("String.inp");
    fin >> X >> Y;
    fin.close();

    int result = solve(X, Y);

    ofstream fout("String.out");
    fout << result << endl;
    fout.close();

    return 0;
}