Java代码的局部比对

接下来你要做的就是找到一个实际的LCS。你这样做在回溯步骤中使用细胞指针,你画了。当你建立你的表,记住,当你左上侧单元格有一个指针,和当前单元格中的值是1超过左上侧单元格的值,这意味着左侧字符以上都是平等的。在建立LCS,这对应于这个角色添加到LCS。因此,构建LCS的方式是通过右下角的单元格开始,然后向后箭头。每次你跟着一个指针左上侧单元格对角线和单元格的值小于1当前单元格的值,将相应的共性的LCS你构造。注意,您预先考虑它,因为你从LCS的结束。(在图5中,右下角的5对应于你的第5个字符。)所以,继续建立你的LCS。从右下角,你看到,指针指向上侧的单元格,当前单元格中的值(5)是一个大于左上侧单元格中的值(4)。所以将字符G的初始零长度字符串。下一个箭头,从细胞包含4,也分左,但并没有改变的价值。和下一个细胞还指出,以上左边,但其价值也不改变。最后,细胞还指出,上述和离开,但从3到4。这意味着您添加行和列的共同特征,这是一个a。所以,到目前为止你LCS是AG)。从那里,沿着指针向左(对应于跳过上面的T)到另一个3。然后有一个对角指针指向2。因此,您添加普通信在当前行和列,这是一个C,产生的牢笼。你以这种方式继续,直到你终于达到0。图6显示了整个回溯: