TopCoder

User's AC Ratio

7.1% (8/112)

Submission's AC Ratio

8.1% (88/1093)

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, M\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 1

2
9 9
cateatdog
dogeatcat
3 6
mEO
Me0Www

Sample Output 1

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。

如果發現程式 Runtime Error,也有可能是你向 Judge 要太多記憶體了(儘管上面顯示的數字沒有到 Memory Limit)

Problem Source

Subtasks

No. Testdata Range Score
1 0 1
2 1~2 13
3 1~4 12
4 5~6 9
5 1~8 28
6 1~10 20
7 0~12 17

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5500 4400 262144 1 7
1 1500 32768 262144 2 3 5 6 7
2 1500 32768 262144 2 3 5 6 7
3 1500 32768 262144 3 5 6 7
4 1500 32768 262144 3 5 6 7
5 800 32768 262144 4 5 6 7
6 800 32768 262144 4 5 6 7
7 600 32768 262144 5 6 7
8 600 32768 262144 5 6 7
9 2500 4960 262144 6 7
10 2500 4960 262144 6 7
11 13000 4400 262144 7
12 13000 4400 262144 7