Bài toán – Số chung lớn nhất
Cho 2 xâu:
X = x1x2..xM. (Với xi là các kí tự số từ ‘0’ đến ‘9’)
Y = y1y2..yN.( Với yi là các kí tự số từ ‘0’ đến ‘9’)
(M, N <= 250)
Ta gọi: Z = z1z2..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ụ:
String.inp |
String.out |
19012304 034012 |
34 |
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;
}