题意：
给字符串a,b,求长度最短的包含a且包含b的字符串。
分析：
是个LCS的对偶问题，dp的方程也很像。
代码：
//poj 2264
//sep9
#include <iostream>
using namespace std;
const int MAXN=128;
int dp[MAXN][MAXN],path[MAXN][MAXN];
char a[MAXN],b[MAXN];
void print(int n,int m)
{if(n==0&&m==0)return ;if(path[n][m]==0){print(n-1,m-1);printf("%c",a[n]);}else if(path[n][m]==-1){print(n,m-1);printf("%c",b[m]);}else{print(n-1,m);printf("%c",a[n]);}}int main()
{while(scanf("%s%s",a+1,b+1)==2){int n=strlen(a+1),m=strlen(b+1);for(int i=1;i<=n;++i)dp[i][0]=i,path[i][0]=1;for(int j=1;j<=m;++j)dp[0][j]=j,path[0][j]=-1;for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){if(a[i]==b[j])dp[i][j]=dp[i-1][j-1]+1,path[i][j]=0;else{if(dp[i][j-1]<dp[i-1][j])dp[i][j]=dp[i][j-1]+1,path[i][j]=-1;elsedp[i][j]=dp[i-1][j]+1,path[i][j]=1;}}print(n,m);puts("");}return 0;
}