Description

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

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

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

因為LCS可能有許多個,請你輸出字典序(Lexicographic Order)最小的一個

若有兩長度相同的字串 X=abcde, Y = accef,因為 $X_2 < Y_2$,我們稱 $X$ 字典序小於 $Y$

Constraints:

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

$N, M \leq 500$

Input Format

$N$

$M$

$A$

$B$

Output Format

字典序最小的LCS

若不存在,輸出 "7122"

Sample Input 1

4
2
abcd
ad

Sample Output 1

ad

Sample Input 2

3
3
abc
def

Sample Output 2

7122

Sample Input 3

5
5
ababa
babab

Sample Output 3

abab

Hints

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

若測資有誤請盡快告知orz

Subtasks

No. Testdata Range Score

TopCoder

AaW
學弟電爛我了

User's AC Ratio

100.0% (3/3)

Tags

Problem Source

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