最长公共子序列全部解

《最长公共子序列全部解》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、最长公共子序列的全部解1、问题描述上次作业最长公共子序列得到了最优值，最优解只得到了一组，而两个序列的最长公共子序列可以有多组，要求打印出两个序列的所有最长公共子序列2、问题分析首先发现这个算法可以简化，去掉数组b，直接用c来判断c[m][n]取决于哪个子序列，通过百度，发现了可以用回溯法来求解，lcs[]用来存放公共字符，当lcs的长度等于已知的最长公共子序列长度则输出子序列。len用来记录lcs长度,len增长到nlen，打印出一组最长子序列。如果在c[m][n]处,c[m-1][n]=c[m][n-1]，也就是在这里出现了分支，那么执行print_all_lcs(m-

2、1,n,curlen)，len增长到nlen，打印出一组子序列后，执行len--，len恢复到出现分支时的值，再接着执行print_all_lcs(m,n-1,curlen)（这是我的理解）下面是按照这个思路的一个程序。voidprint_all_lcs(intm,intn,intcurlen){staticintlen=0;if(m<0

3、

4、n<0)return;if(len==nlen){for(intk=len;k>=0;k--)cout<

5、nt_all_lcs(m-1,n-1,curlen+1);len--;}elseif(c[m-1][n]>c[m][n-1])print_all_lcs(m-1,n,curlen);elseif(c[m-1][n]

6、,intn,intcurlen){if(m<0

7、

8、n<0)return;if(curlen==nlen)//这里不用len来判断{for(intk=nlen;k>=0;k--)cout<c[m][n-1])print_all_lcs(m-1,n,curlen);elseif(c[m-1][n]

9、n);else{print_all_lcs(m-1,n,curlen);print_all_lcs(m,n-1,curlen);}}}