818 . Longest Common Subsequence

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\huge\text{owoovo is 8}$

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

89.5% (17/19)

Tags

apcsc apcsc-dp

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top