转自：http://hzzy-010.blog.163.com/blog/static/79692381200872024242126/
好详细~~~也十分好理解~~~
图 5 的示例中，右下角的 5 与要添加的第 5 个字符对应。）
依此类推，继续构建 LCS。从右下侧的单元格开始，看到单元格指针指向左上侧的单元格，而且当前单元格的值（5）比其左上侧单元格的值（4）大 1。所以将字符 G 添加到最初的零长度的字符串之前。下一个箭头，从包含 4 的单元格开始，也指向左上侧，但是值没有变。接着这个箭头也是如此。下一个单元格的箭头还是指向左上侧，但是这次值从 3 变为 4。这意味着需要将这一行和这一列中的公共字符 A 添加到 LCS 中。所以现在的 LCS 是 AG。接下来，沿着指针向左（对应着跳过上面的 T）到达另一个 3。然后有一个对角指针指向 2。因此，又添加了在当前行和当前列中的公共字符 C，生成的 LCS 为 CAG。继续使用这种方式，直到最后到达 0。图 6 显示了整个回溯过程：
通过这种回溯方法，得到的 LCS 为 GCCAG
代码：
#include <iostream>
#include <string>
#include <cstring>
using namespace std; int c[][];
int b[][]; int LCS_Length(string x,string y)
{
int m=x.length();
int n=y.length();
int i,j; //根据递归方程的第一种情况，先初始化数组c[][]
memset(c,,sizeof(c)); for(i=;i<=m;i++)
for(j=;j<=n;j++)
{
//递归方程case 2
if(x[i-] == y[j-])
{
c[i][j]=c[i-][j-]+;
b[i][j]=; //表示↖
}
else if(c[i-][j] >= c[i][j-]) //下面是递归方程case3
{
c[i][j]=c[i-][j];
b[i][j]=; //表示↑
}
else
{
c[i][j]=c[i][j-];;
b[i][j]=; //表示←
}
}
return c[m][n];
} //输出最优解
void Print_LCS(string X,int i,int j)
{
if( (i == ) || (j == ) )
return;
if(b[i][j] == )
{
Print_LCS(X,i-,j-);
cout<<X[i-]<<" ";
}
else if(b[i][j] == )
Print_LCS(X,i-,j);
else
Print_LCS(X,i,j-);
} int main()
{
string X,Y;
while(cin>>X>>Y)
{
int p=LCS_Length(X,Y);
cout<<"这两个字符串的LCS为："<<p<<endl;
cout<<"该公共子序列为：";
Print_LCS(X,X.length(),Y.length());
cout<<endl;
}
return ;
}
