问题说明：给出两个序列，例如X=“ABCBDAB”、Y=“BDCABA”，并求出它们的最长公共子序列的长度。
以下是求解时的动态计划表，可以看出x和y的最长公共子序列的长度为4。
输出最长的公共子序列并不难。 (互联网上的许多相关代码)，但由于LCS通常不是唯一的，所以输出所有最长的公共子序列是一个难点。
需要在动态计划表中进行回溯——。 如果c[m][n]，即从右下方的方格开始，对应于方格c[i][j]的X[i-1]==Y[j-1]，则将该字符放入LCS中，然后跳到c[i-1][j-1] 如果c[i-1][j]等于c[i][j-1]，则由于有多个最长公共子串，所以两侧都进行回溯(这里使用递归)。 按相反顺序输出LCS，直到I或j小于或等于0。
通过上图中的红色路径，可以看到x和y的最长公共子序列为“BDAB”、“BCAB”和“BCBA”三个。
c代码：
# include bits/stdc.husingnamespacestd； 字符串x； 字符串y； vectorvectorint c； //动态计划表setstring lcs； //set所有LCSintLCS_length(intm，int n ) /表的大小为(m 1 ) * (n1 ) c=vectorvectorint(m1，vectorint ) (n1 ) )； for(intI=0； im 1； I ) for(intj=0； jn 1； 在j () /第1行和第1列中输入0if(I==0||j==0) c[i][j]=0； elseif(x[I-1]==y[j-1] ) c[I] ) j )=c[I-1](j-1 ) 1； elsec[I][j]=max(c[I-1][j]，c[i][j-1] )； }}return c[m][n]； }在}voidLCS_print(intI，int j，string lcs_str ) while(I0J0) if ) x(I-1 )==y(j-1 ) ) LCS_str.pussr -I； -j； }else{if(c[I-1][j]c[I][j-1] )--i； elseif(c[I-1][j]c[I][j-1] )-j； ELSE{LCS_print(I-1，j，lcs_str )； LCS_print(I，j-1，lcs_str )； 返回； }}}//coutlcs_strendl； reverse(LCS_str.begin )、lcs_str.end )； LCS.insert(LCS_str； (}int main ) ) {cinXY； int m=X.length (； int n=Y.length (； intlength=LCS_length(m，n )； cout ' thelengthoflcsis ' length endl； 字符串str； LCS_print(m，n，str )； setstring :迭代器it=LCS.begin (； for (； 信息技术！=lcs.end (； it ) cout *it endl； 返回0； )执行效果：