Bài toán: Xâu con chung dài nhất (LCS)

Cho hai xâu ký tự S và T chỉ gồm các chữ cái in thường tiếng Anh.

Hãy tìm độ dài của xâu con chung dài nhất của S và T.

Xâu con chung dài nhất (Longest Common Subsequence - LCS) là dãy ký tự xuất hiện theo đúng thứ tự trong cả hai xâu, nhưng không nhất thiết liên tiếp.

Input

• Dòng 1 chứa xâu S.
• Dòng 2 chứa xâu T.

Output

• In ra một số nguyên là độ dài của xâu con chung dài nhất của S và T.

Ràng buộc

• 1 ≤ |S|, |T| ≤ 1000
• S, T chỉ gồm các ký tự từ 'a' đến 'z'

Ví dụ

Input

abcbdab
bdcaba

Output

4

Giải thích

Một LCS có thể là bcba hoặc bdab, đều có độ dài 4.

Gợi ý thuật toán

Đặt dp[i][j] là độ dài LCS của hai tiền tố:

• S[1..i]
• T[1..j]

Khi đó:

• Nếu S[i] == T[j] thì dp[i][j] = dp[i-1][j-1] + 1
• Ngược lại dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Đáp án là dp[|S|][|T|].