序列比较是生物信息学中一个非常重要的概念，在生物数据的分析起着不可或缺的作用。目前，绝大多数序列比较工具都包含了基于动态规划的序列比较步骤。序列比较问题类似于最长的公共子序列问题 （Longest Common Subsequence problem, LCS) ，然后衍生出尼德曼-翁施算法的全局比较算法 （Needleman-Wunsch Algorithm） 史密斯-沃特曼算法与局部比较 （Smith-Waterman algorithm） 。

若给出序列 X = { x 1 , x 2 , . . . , x m } X = \{x_1,x_2,...,x_m\} X={ x1,x2,...,xm}，还有另一个序列 Z = { z 1 , z 2 , . . . , z k } Z=\{z_1,z_2,...,z_k\} Z={ z1 ,z2​,...,zk​}, 存在严格递增的下标序列 { i 1 , i 2 , . . . , i k } \{i_1,i_2,...,i_k\} { i1​,i2​,...,ik​}，并且对于$j=1,2,...,k$有$z_j=x_{i_j}$，那么称序列$Z$为序列$X$的子序列。如序列 Z = { B , C , D , B } Z = \{B,C,D,B\} Z={ B,C,D,B}为序列 X = { A , B , C , B , D , A , B } X=\{A,B,C,B,D,A,B\} X={ A,B,C,B,D,A,B}的子序列，并且存在对应的递增下标序列 { 2 , 3 , 5 , 7 } \{2,3,5,7\} { 2,3,5,7}。

给出两条序列$X$和$Y$，如果序列$Z$是序列$X$和$Y$的共同的子序列，则称$Z$为序列$X$和$Y$的公共子序列。
设 Z = { z 1 , z 2 , . . . , z k } Z=\{z_1,z_2,...,z_k\} Z={ z1​,z2​,...,zk​}是序列 X = { x 1 , x 2 , . . . , x m } X=\{x_1,x_2,...,x_m\} X={ x1​,x2​,...,xm​}与序列 Y = { y 1 , y 2 , . . . , y n } Y=\{y_1,y_2,...,y_n\} Y={ y1​,y2​,...,yn​}的最长公共子序列，则有：
（1）如果$x_m=y_n$，则有$z_k=x_m=y_n$，并且$Z_{k-1}$是序列$X_{m-1}$与$Y_{n-1}$的最长公共子序列；
（2）如果$x_m\ne y_n$，且$z_k\ne x_m$，则序列$Z$是序列$X_{m-1}$和序列$Y$的最长公共子序列；
（3）如果$x_m\ne y_n$，且$z_k\ne y_n$，则序列$Z$是序列$X$和序列$Y_{n-1}$的最长公共子序列；