Giải thích các bước giải:

 Đây là bài toán kinh điển về Quy hoạch động (Dynamic Programming) tìm độ dài xâu con chung dài nhất (Longest Common Subsequence - LCS).Dưới đây là lời giải chi tiết, thuật toán và mã nguồn Python được viết hoàn toàn bằng chữ thường và văn bản thuần túy không định dạng để bạn dễ dàng sao chép:Ý tưởng thuật toán:
Chúng ta sẽ dùng một bảng hai chiều (ma trận) để lưu trữ kết quả trung gian. Gọi m là độ dài xâu A, n là độ dài xâu B. Chúng ta tạo bảng dp có kích thước m cộng 1 hàng và n cộng 1 cột, ban đầu tất cả các ô bằng 0.Hàng i và cột j của bảng dp sẽ lưu độ dài xâu con chung dài nhất của đoạn đầu xâu A dài i ký tự và đoạn đầu xâu B dài j ký tự.
Chúng ta duyệt qua từng ký tự của xâu A và xâu B:
Trường hợp 1: Nếu ký tự thứ i trừ 1 của xâu A bằng ký tự thứ j trừ 1 của xâu B, thì ô dp tại hàng i cột j sẽ bằng ô dp tại hàng i trừ 1 cột j trừ 1 cộng thêm 1.
Trường hợp 2: Nếu hai ký tự không bằng nhau, thì ô dp tại hàng i cột j sẽ bằng giá trị lớn nhất giữa ô ngay phía trên nó (hàng i trừ 1 cột j) và ô ngay bên trái nó (hàng i cột j trừ 1).
Kết quả cuối cùng chính là giá trị nằm ở ô dưới cùng bên phải của bảng (hàng m cột n).Dưới đây là mã nguồn Python hoàn chỉnh:def solve():
a = input().strip()
b = input().strip()m = len(a)
n = len(b)dp = [[0] * (n + 1) for _ in range(m + 1)]for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])print(dp[m][n])if name == 'main':
solve()