4467 . LCS練習 (Easy Version)

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
$\Huge\text{freeh1}$

User's AC Ratio

91.7% (11/12)

Submission's AC Ratio

48.8% (20/41)

Tags

Low DP

Description

三子題的輸入輸出要求皆不同，請看清楚題目再Submit

LCS(Longest Common Subsequence)，最長共同子序列

顧名思義，給你兩個小寫英文字母的字串 $A, B$，找出他們的LCS長度

Constraints:

$|A| = N, |B| = M$

$N, M \leq 500$

Input Format

$N$

$M$

$A$

$B$

Output Format

$A$ 和 $B$ 的 LCS 長度

Sample Input 1

4
2
abcd
ad

Sample Output 1

2

Sample Input 2

3
3
abc
def

Sample Output 2

0

Sample Input 3

4
4
abab
baba

Sample Output 3

3

Hints

子序列(Subsequence) 不一定要連續，但順序不能交換

Problem Source

Subtasks

No. Testdata Range Score

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 250000 250000 65536
1 1000 250000 250000 65536
2 1000 250000 250000 65536
3 1000 250000 250000 65536
4 1000 250000 250000 65536
5 1000 250000 250000 65536
6 1000 250000 250000 65536
7 1000 250000 250000 65536
8 1000 250000 250000 65536
9 1000 250000 250000 65536
10 1000 250000 250000 65536
11 1000 250000 250000 65536
12 1000 250000 250000 65536
13 1000 250000 250000 65536
14 1000 250000 250000 65536
Submit
Back to Top