Longest common subsequence problem

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences). It differs from the longest common substring problem: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.

Example

• LCS for input Sequences ABCDGH and AEDFHR is ADH of length 3.
• LCS for input Sequences AGGTAB and GXTXAYB is GTAB of length 4

以s1={1,3,4,5,6,7,7,8},s2={3,5,7,4,8,6,7,8,2}为例。

1.构建二维矩阵A[n+1][n+1] s1为列，s2为行

（1）A[0][any]=0,A[any][0]=0

（2）if(s1[columnIndex-1]==s2[rowIndex-1])则A[columnIndex][rowIndex]=A[columnIndex-1][rowIndex-1]+1;

         else  A[columnIndex][rowIndex]=max(A[columnIndex-1][rowIndex],A[columnIndex][rowIndex-1])

 （3）由A[8][9]可知最大子序列长度。

图如下：