這題要用到最長公共子序列，又是DP，可是不會，於是就去學這個，看了一會兒，終於有點心得了。
主體思想就是先求出最長公共子序列，然後把公共字符之前的所有字符都合並起來。具體請看下面的注釋。
#include
#include
const int N=105;
char s1[N],s2[N],s[N*2];
int lcs[N][N],index1[N],index2[N];//index和index2是用來記錄公共字符所在的索引。
void get_lcs()
{
int len1=strlen(s1);
int len2=strlen(s2);
memset(lcs,0,sizeof(lcs));
for(int i=1;i<=len1;i++)//求出最長公共子序列的長度
{
for(int j=1;j<=len2;j++)
{
if(s1[i-1]==s2[j-1])
lcs[i][j]=lcs[i-1][j-1]+1;
else
{
if(lcs[i-1][j]>lcs[i][j-1])
lcs[i][j]=lcs[i-1][j];
else
lcs[i][j]=lcs[i][j-1];
}
}
}
int i=len1-1,j=len2-1,top=0;
while(i!=-1&&j!=-1)//求出所有公共字符的索引
{
if(s1[i]==s2[j])
{
index1[top]=i,index2[top]=j;
top++,i--,j--;
}
else
{
if(lcs[i+1][j+1]==lcs[i][j])
i--,j--;
else
{
if(lcs[i+1][j]>lcs[i][j+1])
j--;
else
i--;
}
}
}
index1[top]=-1,index2[top]=-1;//設置這個是為了合並第一個公共字符之前的字符
//for(int i=0;i<=top;i++)
//printf("%d,index1=%d,index2=%d\n",i,index1[i],index2[i]);
int s_top=0;
for(int i=top;i>=1;i--)
{
for(int j=index1[i]+1;j
