http://acm.hdu.edu.cn/showproblem.php?pid=1503
题意：
给出两个串，现在要确定一个尽量短的串，使得该串的子串包含了题目所给的两个串。
思路：
这道题目就是要我们求LCS，记录好路径就好。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int INF = 0x3f3f3f3f;
const int maxn = + ; char s1[maxn],s2[maxn];
int d[maxn][maxn];
int mark[maxn][maxn]; void LCS(int n, int m)
{
memset(d,,sizeof(d));
for(int i = ;i<=n;i++)
mark[i][] = ;
for(int i = ;i<=m;i++)
mark[][i] = ; for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(s1[i]==s2[j])
{
d[i][j]=d[i-][j-]+;
mark[i][j]=;
}
else
{
if(d[i-][j]>d[i][j-])
{
d[i][j]=d[i-][j];
mark[i][j]=;
}
else
{
d[i][j]=d[i][j-];
mark[i][j]=;
}
}
}
}
} void print(int i,int j)
{
if(i== && j==) return;
if(mark[i][j]==)
{
print(i-,j-);
printf("%c",s1[i]);
}
else if(mark[i][j]==)
{
print(i-,j);
printf("%c",s1[i]);
}
else
{
print(i,j-);
printf("%c",s2[j]);
}
} int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%s%s",s1+,s2+))
{
int len1=strlen(s1+);
int len2=strlen(s2+); LCS(len1,len2);
print(len1,len2);
printf("\n");
}
return ;
}