题意：将两个字符串合成一个串，不改变原串的相对顺序，可将相同字母合成一个，求合成后最短的字符串。
题解：LCS有三种状态转移方式，将每个点的状态转移方式记录下来，再回溯。
#include <bits/stdc++.h>
using namespace std; const double EPS = 1e-;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + ;
const int maxn = + ;
char s[maxn], t[maxn];
int slen, tlen;
int dp[maxn][maxn], p[maxn][maxn]; void LCS()
{
memset(dp, , sizeof(dp));
for(int i = ; i <= slen; i++) p[i][] = ;
for(int i = ; i <= tlen; i++) p[][i] = -; for(int i = ; i <= slen; i++){
for(int j = ; j <= tlen; j++){
if(s[i] == t[j]){
dp[i][j] = dp[i-][j-] + ;
p[i][j] = ;
}
else if(dp[i-][j] >= dp[i][j-]){
dp[i][j] = dp[i-][j];
p[i][j] = ;
}
else{
dp[i][j] = dp[i][j-];
p[i][j] = -;
}
}
}
} void PrintLcs(int i, int j)
{
if(!i && !j) return ;
if(p[i][j] == ){
PrintLcs(i-, j-);
putchar(s[i]);
}
else if(p[i][j] == ){
PrintLcs(i-, j);
putchar(s[i]);
}
else if(p[i][j] == -){
PrintLcs(i, j-);
putchar(t[j]);
}
} int main()
{
while(scanf("%s%s", s + , t + ) != EOF){
slen = strlen(s + );
tlen = strlen(t + ); LCS();
PrintLcs(slen, tlen); puts("");
} return ;
}