818 . Longest Common Subsequence
Description
JOI 君很喜歡字串，有一天，他收到了別人送的禮物，兩個字串 $A, B$！
於是 JOI 君很好奇，這兩個字串的最長共同子序列長度是多少？
一個字串 $T$ 是一個字串 $S$ 的子序列，若且唯若我們刪除零或多個在 $S$ 字串中的字元後，可以得到字串 $T$。
舉例來說 abc 是 accbddc 的子序列，因為刪除 ccdd 後，accbddc 就會變成 abc。
假如 $T$ 同時是 $A, B$ 字串的子序列，我們就說 $T$ 是 $A, B$ 字串的共同子序列。
Input Format
輸入只有一行，有兩個字串 $A, B$ 以一個空白隔開。
其中 $1 \le |A|, |B| \le 5000$。
且 $A, B$ 字串都會由英文小寫字母組成。
注意到 $|S|$ 代表的是字串 $S$ 的長度。
Output Format
輸出一行一個整數代表答案。
Sample Input 1
abc accbddc
Sample Output 1
3
Sample Input 2
aabbcc aaddeebc
Sample Output 2
4
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~20 | 無額外限制 | 100 |