Xâu con chung dài nhất

Trung bình

quy hoạch độngchuỗi5 test · 3 giây

Cho hai chuỗi a và b. Tìm độ dài xâu con chung dài nhất — chuỗi nhận được từ cả a và b bằng cách xóa bớt một số ký tự (giữ nguyên thứ tự).

dp[i][j] = độ dài LCS của a[0..i) và b[0..j). Chỉ cần giữ hai hàng → bộ nhớ O(|b|).

Dữ liệu vào

Dòng 1: chuỗi a. Dòng 2: chuỗi b. (1 ≤ độ dài ≤ 1500, chữ cái thường)

Một số nguyên.

Input

abcde
ace

Output

"ace"

Input

abc
def

Output

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

# Đọc dữ liệu từ input(), in kết quả bằng print()
import sys

def main():
    data = sys.stdin.read().split()
    # TODO: xử lý


main()

Input (stdin)

Output

Bấm “Chạy thử” để xem kết quả với input bên trái.