学步园

http://acm.hdu.edu.cn/showproblem.php?pid=1503

解题思路：这道题就是给你两个单词，然后你要把两个单词拼接成一个新单词，使得新单词的子序列中包含两个单词，并且要使这个新单词最短。所以这道题就是求最长公共子序列，并且要记录下子序列的字母，以及他们在主串和副串中的原始位置，之后进行拼接输出。

#include <stdio.h><br /> #include <string.h><br /> #define size 201</p> <p>int Max(int x,int y)<br /> {<br /> return x>y?x:y;<br /> }</p> <p>struct rem<br /> {<br /> int i,j;/*i记录主串位置，j记录副串当前字符位置*/<br /> char ch;/*记录当前字符*/<br /> };</p> <p>char a[size],b[size];<br /> int dp[size][size];<br /> rem ans[size];<br /> int len;/*指示ans的长度*/</p> <p>void lcs(int m,int n)<br /> {<br /> int i,j;<br /> memset(dp,0,sizeof(dp));<br /> len = 0;<br /> for (i=1;i<=m;i++)<br /> {<br /> for (j=1;j<=n;j++)<br /> {<br /> if(a[i]==b[j])<br /> dp[i][j] = dp[i-1][j-1]+1;<br /> else<br /> dp[i][j] = Max(dp[i-1][j],dp[i][j-1]);<br /> }<br /> }<br /> if(dp[m][n] == 0)/*如果没有公共序列，直接输出*/<br /> printf("%s%s",a,b);<br /> else<br /> {<br /> /*取出最长公共子序列的字母*/<br /> i = m,j = n;<br /> while (i!=0&&j!=0)<br /> {<br /> if ((dp[i][j] = dp[i-1][j-1]+1)&&a[i] == b[j])<br /> {<br /> ans[len].i = i;<br /> ans[len].j = j;<br /> ans[len++].ch = a[i];/*倒序保存最长公共子序列字母*/<br /> i--,j--;<br /> }<br /> else if(dp[i-1][j]>dp[i][j-1])<br /> i--;<br /> else<br /> j--;<br /> }<br /> /*取出最长公共子序列的字母*/<br /> }<br /> }</p> <p>int main()<br /> {<br /> int a1,b1,i,j,k;<br /> while (scanf("%s%s",a+1,b+1)!=EOF)<br /> {<br /> a1 = strlen(a+1);<br /> b1 = strlen(b+1);<br /> lcs(a1,b1);<br /> i = j = 1;<br /> for (k=len-1;k>=0;k--)<br /> {<br /> while (i!=ans[k].i)<br /> {<br /> printf("%c",a[i]);<br /> i++;<br /> }<br /> while (j!=ans[k].j)<br /> {<br /> printf("%c",b[j]);<br /> j++;<br /> }<br /> printf("%c",ans[k].ch);<br /> i++,j++;<br /> }<br /> printf("%s%s/n",a+ans[0].i+1,b+ans[0].j+1);<br /> }<br /> return 0;<br /> }