40010. Practice 10: 最長共同子序列

I'm a slow walker, but I never walk backwards.

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

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

注意本題總共有120分。因為記憶體限制的關係,想要拿到超過100分的同學,請使用scanf/printf輸入、輸出,並且不要引入<iostream><bits/stdc++.h>兩個標頭檔

Input/Output

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

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

Subtasks/Constraints

所有測資皆符合: $T\leq 10, N\leq 10000$

  1. 兩個字串相同 (5 pts)
  2. $N,M\leq 8$ (15 pts)
  3. $N\leq 8, M\leq 2000$ (15 pts)
  4. $N,M\leq 500$,且$A,B$只由ab兩種字元構成 (25 pts)
  5. $N,M\leq 2000$ (45 pts)
  6. $N,M\leq 4000$ (5 pts)
  7. 無額外限制 (10 pts)

Sample Input

2
9 9
cateatdog
dogeatcat
3 6
mEO
Me0Www

Sample Output

atat
*

Discussion