Xâu con chung dài nhất - LCOJ: Luyện Code Online Judge

SUBSTR - Xâu con chung dài nhất

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

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~ chỉ gồm các chữ cái latin và chữ số, 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 đầu chứa xâu ký tự ~A~;
Dòng thứ hau chứa xâu ký tự ~B~.

Giới hạn:

Độ dài các xâu ~A, B~ không vượt quá ~2000~.

Output

Mộ dòng duy nhất ghi độ dài xâu ~C~ tìm được.

Sample

Input #1

abc1def2ghi3
abcdefghi123

Output #1

Problem source: Chuyên Sơn La Online Judge

Bình luận

Please read the guidelines before commenting.

tranvandoan1802 đã bình luận lúc 19, Tháng 1, 2026, 2:45 ← chỉnh sửa →

'''#include <bits/stdc++.h> using namespace std ;

int main() { ios::syncwithstdio(false); cin.tie(0) ; cout.tie(0);

string x , y ;
cin >> x >> y ;

int n = x.size() ;
int m = y.size();

int dp[3000][3000];
// khởi tạo hàng 0 và cột không 
for(int i = 0 ; i <= n ; i++) dp[i][0] = 0;
for(int j = 0 ; j <= m ; j++) dp[0][j] = 0;

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {

        // TH1: ký tự cuối giống nhau
        if (x[i - 1] == y[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        // TH2: ký tự cuối khác nhau
        else {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
}

// Kết quả
cout << dp[n][m];

} '''c++

include <bits/stdc++.h>

using namespace std;

int main() { string s1, s2; cin >> s1 >> s2; int n = s1.size(), m = s2.size();

vector<vector<int>> dp(n+1, vector<int>(m+1, 0));

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    }
}

cout << dp[n][m];
return 0;

}

0

wi86lll đã bình luận lúc 12, Tháng 4, 2025, 12:51

Wait what??

0

vutientuan_001 đã bình luận lúc 3, Tháng 9, 2025, 14:53

sao vậy bro