題目描述

給出兩個字串 S₁, S₂ 求最長公共子序列 ( Longest Common Subsequence, LCS ) 的長度，
它與子串不同的時, 子序列並不要求連續, 只要順序不變即可。

例如字串 ABC 它的子序列分別是：

• ABC
• AB
• BC
• AC
• A
• B
• C
• 空字串 ( 表示該字串沒有任何字符 )

所以對於 ABC 和 空字串 這兩個情況，
又會有 真子序列 ( 即不包括自身 ) 和 非空子序列 ( 即不包括空字串 ) 的說法。

輸入格式

兩行，每行一段非空字串

輸出格式

一行，一個整數，表示最長的公共子序列

Samples

ZZIQGIGGZN
UAZBZCZ

3

原始資料

• Zero1 題號：a527
• Hydro 題號：Z0527
• Locale：zh_TW
• Display：practice