Độ dài chuỗi chung ngắn nhất

Bối cảnh và bài toán

Cần tạo một chuỗi chứa cả s và t như các dãy con.

Yêu cầu

Tìm độ dài nhỏ nhất của một chuỗi như vậy.

Input

Hai dòng s, t.

Output

In độ dài nhỏ nhất.

Ràng buộc

• 1 <= |s|,|t| <= 3000
• Chuỗi chữ thường.

Chấm điểm

Ví dụ 1

Input

abac
cab

Output

5

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

abc
abc

Output

3

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.