Xâu con chung dài nhất - LCOJ: Luyen Code Online

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ả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, ~~PHP~~, 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

Hãy đọc nội quy trước khi bình luận.

C++ full AC

#include <iostream>

using namespace std;

int main() {
    string s1,s2;
    cin >> s1 >> s2;
    int n = s1.size();
    int m = s2.size();
    s1 = "x" + s1;
    s2 = "x" + s2;
    int F[n+1][m+1];
    for (int i = 0 ; i <= n; i++) F[i][0] = 0;
    for (int i = 0 ; i <= m; i++) F[0][i] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i] == s2[j]) {
                F[i][j] = F[i - 1][j - 1] + 1;
            } else {
                F[i][j] = max(F[i][j - 1], F[i - 1][j]);
            }
        }
    }
    cout << F[n][m];
    return 0;
}