TopCoder

Thumb
柊 四千
あぅあぅ~

User's AC Ratio

50.0% (3/6)

Submission's AC Ratio

19.4% (7/36)

Tags

Description

給你兩個字串$A,B$,請輸出它們的一個「最長共同子序列」(LCS)。

一個字串的子序列的是把它其中一些字元刪去所得到的新字串(可以不刪去任何字元,也可以刪去所有字元)。
如果有一個字串$C$同時是$A,B$的子序列,我們稱$C$是$A,B$的「共同子序列」。兩字串的「最長共同子序列」即是它們所有的共同子序列中最長的一個。

注意:本題請勿使用任何動態記憶體配置(包含newmallocstd::allocator等)。使用C++作答的同學,請在程式碼開頭加上#include <cstdio>,並利用scanf讀入資料、用printf輸出資料scanfprintf的使用方式在下方Hints中有陳述。
若你使用了<iostream><bits/stdc++.h>標頭檔或任何的動態記憶體配置,極有可能會因為效率太差以致於程式執行時間、空間超過限制。
如果你需要使用<bits/stdc++.h>,請在引入該標頭檔前加上一行#define _GLIBCXX_IOSTREAM

Input Format

第一行有一個正整數$T$,代表共有幾個測資。

對於每個測資,第一行有兩個以空白隔開的正整數$N,M$,代表兩個字串的長度;第二行和第三行則分別是由大小寫英文字母與數字構成的字串$A,B$。

對於所有測資,$T\leq 10, N\leq 10000$。

子任務(測資) 額外限制 分數
1 (0) 兩個字串相同 1
2 (1~2) $N,M\leq 8$ 13
3 (1~4) $N\leq 8, M\leq 2000$ 12
4 (5~6) $N,M\leq 500$
只有a,b兩種字元
9
5 (1~8) $N,M\leq 2000$ 28
6 (1~10) $N,M\leq 4000$ 20
7 (0~12) 無限制 17

Output Format

對於每個測資輸出一行包含一個字串,代表$A,B$的一個最長共同子序列。如果有很多個,輸出任何一個都可以。
如果兩者的最長共同子字串是空字串,請輸出一行*

Sample Input

2
9 9
cateatdog
dogeatcat
3 6
mEO
Me0Www

Sample Output

atat
*

Hints

scanf 常用的讀入方式如下:
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%s",str); 讀入一個字串至char陣列str。

printf 常用的輸出方式如下:
printf("%d\n",x); 輸出一行包含一個int 型態變數x。
printf("%s\n",str); 輸出一行包含一個字串str。

Problem Source

Subtasks

For Testdata: 0 ~ 0, Score: 1
For Testdata: 1 ~ 2, Score: 13
For Testdata: 1 ~ 4, Score: 12
For Testdata: 5 ~ 6, Score: 9
For Testdata: 1 ~ 8, Score: 28
For Testdata: 1 ~ 10, Score: 20
For Testdata: 0 ~ 12, Score: 17
No. Time Limit (ms) Memory Limit (KiB)
0 5500 4400
1 1500 32768
2 1500 32768
3 1500 32768
4 1500 32768
5 800 32768
6 800 32768
7 600 32768
8 600 32768
9 2500 4960
10 2500 4960
11 13000 4400
12 13000 4400