題目描述

給定兩個字符串s和t，求出它們的最長公共子序列的長度。最長公共子序列是指在兩個字符串中都出現過，且保持相對順序不變的最長的子序列。例如，“abcde"和"ace"的最長公共子序列是"ace”，長度為3。 

輸入格式

輸入包含兩行，分別是字符串s和t。字符串只包含小寫英文字母。 

限制條件：1 <= len(s), len(t) <= 1000 

輸出格式

輸出一個正整數，表示最長公共子序列的長度。 

Samples

abcde
ace

3

提示

動態規劃

原始資料

• Zero1 題號：b039
• Hydro 題號：Z1039
• Locale：zh_TW
• Display：open