2010 . 最長共同子序列（LCS）
TopCoder
Description
給你兩個字串$A,B$，請輸出它們的一個「最長共同子序列」（LCS）。
一個字串的子序列的是把它其中一些字元刪去所得到的新字串（可以不刪去任何字元，也可以刪去所有字元）。
如果有一個字串$C$同時是$A,B$的子序列，我們稱$C$是$A,B$的「共同子序列」。兩字串的「最長共同子序列」即是它們所有的共同子序列中最長的一個。
注意：本題請勿使用任何動態記憶體配置（包含new、malloc、std::allocator等）。使用C++作答的同學，請在程式碼開頭加上#include <cstdio>，並利用scanf讀入資料、用printf輸出資料。scanf與printf的使用方式在下方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
9 9
cateatdog
dogeatcat
3 6
mEO
Me0Www
Sample Output 1
*
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 |