Cho hai xâu ký tự ~a~ và ~b~.
Ta muốn tìm một xâu ký tự có thể thu được từ cả hai xâu bằng cách xóa đi một số (có thể là 0) ký tự bất kỳ, nhưng vẫn giữ nguyên thứ tự các ký tự còn lại.

Xâu thu được từ ~a~ và từ ~b~ giống hệt nhau và có độ dài lớn nhất được gọi là xâu con chung dài nhất, hay LCS (Longest Common Subsequence).

Lưu ý:

• Xâu con trong bài toán này là xâu con theo nghĩa subsequence, tức là các ký tự không cần đứng liền nhau trong xâu gốc.
• Khác với substring là xâu con liên tiếp.

Ví dụ:

• ~a = abcde~, ~b = ace~
  Một xâu con chung dài nhất là ~ace~, có độ dài ~3~.

• ~a = abc~, ~b = def~
  Không có ký tự chung nên độ dài ~\text{LCS}~ bằng ~0~.

Yêu cầu

Cho hai xâu ký tự ~a~ và ~b~.
Hãy tính độ dài của xâu con chung dài nhất của ~a~ và ~b~.

Nói cách khác, hãy tìm số nguyên không âm ~L~ lớn nhất sao cho tồn tại một xâu ~s~ có độ dài ~L~, ~s~ là xâu con của ~a~ và đồng thời cũng là xâu con của ~b~.

Dữ liệu

• Dòng thứ nhất: xâu ký tự ~a~.
• Dòng thứ hai: xâu ký tự ~b~.

Giới hạn:

• ~1 \le |a|, |b| \le 1000~.
• Các ký tự thuộc bộ ký tự thông dụng (ví dụ bảng chữ cái tiếng Anh, chữ số, ký tự ASCII), tuỳ theo hệ thống chấm.

Kết quả

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

Ví dụ

Ví dụ 1

Input

abcde
ace

Output

3

Ví dụ 2

Input

abc
def

Output

0

Ví dụ 3

Input

AGGTAB
GXTXAYB

Output

4

Giải thích

Giải thích ví dụ 1

Ta có:

• ~a = abcde~
• ~b = ace~

Một xâu con chung dài nhất là ~ace~, nên độ dài bằng ~3~.

Giải thích ví dụ 2

Ta có:

• ~a = abc~
• ~b = def~

Không có ký tự nào xuất hiện trong cả hai xâu, nên không tồn tại xâu con chung khác rỗng.
Vì vậy, độ dài ~\text{LCS}~ bằng ~0~.

Giải thích ví dụ 3

Ta có:

• ~a = AGGTAB~
• ~b = GXTXAYB~

Một xâu con chung dài nhất có thể là ~GTAB~, có độ dài ~4~.
Không có xâu con chung nào có độ dài lớn hơn, nên đáp án là ~4~.

Gợi ý thuật toán Quy hoạch động

Ký hiệu:

• ~n = |a|~ là độ dài xâu ~a~.
• ~m = |b|~ là độ dài xâu ~b~.

Xây dựng bảng hai chiều ~f~ kích thước ~(n + 1) \times (m + 1)~, trong đó:

• ~f[i][j]~ là độ dài xâu con chung dài nhất của hai xâu con ~a[1..i]~ và ~b[1..j]~.

Khi đó, ta có công thức quy hoạch động:

• Nếu ~a[i] = b[j]~ thì:

$$ f[i][j] = f[i - 1][j - 1] + 1. $$

• Ngược lại:

$$ f[i][j] = \max\bigl(f[i - 1][j], f[i][j - 1]\bigr). $$

Điều kiện biên:

• ~f[0][j] = 0~ với mọi ~0 \le j \le m~.
• ~f[i][0] = 0~ với mọi ~0 \le i \le n~.

Đáp án cuối cùng là:

$$ \text{LCS\_len} = f[n][m]. $$

Độ phức tạp:

• Thời gian: ~O(n \cdot m)~ với ~n, m \le 1000~ là phù hợp.
• Bộ nhớ: ~O(n \cdot m)~. Có thể tối ưu xuống ~O(\min(n, m))~ nếu chỉ lưu hai dòng của bảng.