Bài toán tìm xâu con chung dài nhất năm 2024

Điểm: 400 [p] Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho hai xâu \[s\] và \[t\] chỉ gồm các chữ cái thường \['a'..'z'\]. Tìm xâu con chung dài nhất [subsequence] của hai xâu \[s\] và \[t\]

Input

• Dòng thứ nhất chứa xâu \[s[1\le |s|\le 3000]\]
• Dòng thứ hai chứa xâu \[t[1\le |t|\le 3000]\]

Output

• In ra xâu chung dài nhất cần tìm. Nếu có nhiều đáp án in ra bất kì !

Chú ý: Một xâu con của một xâu \[x\] bất kì thu được bằng cách xóa đi một vài kí tự [có thể không xóa kí tự nào] từ xâu \[x\] và nối những phần tử còn lại mà không thay đổi thứ tự của chúng.

Example

Test 1

Input

axyb
abyxb

Output

axb

Note

Giải thích: Ở đây có hai đáp \[axb\] và \[ayb\] đều thỏa mãn nên ta có thể in ra một cái bất kì , trong trường hợp này nó là \[axb\]

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

• Đề bài: //vnoi.info/problems/QBSTR/
• Keywords: lcs, string
• Ngôn ngữ: C++

Công thức tìm xâu con chung dài nhất của 2 xâu A, B:

• Nếu \[A[i] = B[j]\], \[F[i][j] = F[i-1][j-1] + 1\]
• Ngược lại, \[F[i][j] = max\{F[i-1][j], F[i][j-1]\}\]

Open in Github • Download

# include 

# include 

# include 

# include 
using namespace std;
int lcs[string &a, string &b] {
    int m = a.size[], n = b.size[];
    a = ' ' + a;
    b = ' ' + b;
    vector< vector > f[m+1, vector[n+1, 0]];
    for [int i=1; i a;
    string b; cin >> b;
    cout