問題描述
最長公共子序列也稱作最長公共子串(不要求連續)，英文縮寫為LCS（Longest Common Subsequence）。其定義是，一個序列 S ，如果分別是兩個或多個已知序列的子序列，且是所有符合此條件序列中最長的，則 S 稱為已知序列的最長公共子序列。
套用
最長公共子序列是一個十分實用的問題，它可以描述兩段文字之間的“相似度”，即它們的雷同程度，從而能夠用來辨別抄襲。對一段文字進行修改之後，計算改動前後文字的最長公共子序列，將除此子序列外的部分提取出來，這種方法判斷修改的部分，往往十分準確。簡而言之，百度知道、百度百科都用得上。
算法
動態規劃的一個計算兩個序列的最長公共子序列的方法如下：
以兩個序列 X、Y 為例子：
設有二維數組 f[i,j] 表示 X 的 i 位和 Y 的 j 位之前的最長公共子序列的長度，則有：
f[1][1] = same(1,1);
f[i,j] = max{f[i-1][j -1] + same(i,j),f[i-1,j],f[i,j-1]}
其中，same(a,b)當 X 的第 a 位與 Y 的第 b 位完全相同時為“1”，否則為“0”。
此時，f[j]中最大的數便是 X 和 Y 的最長公共子序列的長度，依據該數組回溯，便可找出最長公共子序列。
該算法的空間、時間複雜度均為O(n^2)，經過最佳化後，空間複雜度可為O(n)。
代碼（Pascal）
const
maxlen=200;
var
i,j :longint;
c :array[0..maxlen,0..maxlen] of byte;
x,y,z :string; {z為x,y的最長公共子序列}
begin
readln(x);
readln(y);
fillchar(c,sizeof(c),0);
for i:=1 to length(x) do
for j:=1 to length(y) do
if x[i]=y[j]
then c[i,j]:=c[i-1,j-1]+1
else if c[i-1,j]>c[i,j-1]
then c[i,j]:=c[i-1,j]
else c[i,j]:=c[i,j-1];
z:="";
i:=length(x);
j:=length(y);
writeln(c[i,j]);
while (i>0) and (j>0) do
if x[i]=y[j]
then begin z:=x[i]+z;i:=i-1;j:=j-1 end
else if c[i-1,j]>c[i,j-1]
then i:=i-1
else j:=j-1;
if z<>'' then writeln(z);
for i:=1 to length(x) do
begin
for j:=1 to length(y) do write(c[i][j]:3);
writeln;
end;
readln;
end.
代碼（C++）
#include <cstdlib>
#include <iostream>
using namespace std;
#define N 105
int dp[N+1][N+1] ;
char str1[N] , str2[N];
int MAXX(int a , int b)
{
if(a > b)
return a ;
return b ;
}
int LCSL(int len1 , int len2)
{
int i , j ;
int len = maxx(len1 , len2);
for( i = 0 ; i <= len; i++ )
{
dp[i][0] = 0 ;dp[0][i] = 0 ;
}
for( i = 1 ; i<= len1 ; i++)
for( j = 1 ; j <= len2 ; j++)
{
if(str1[i - 1] == str2[j - 1])
{
dp[i][j] = dp[i - 1][ j - 1] + 1 ;
}
else
{
dp[i][j] = maxx(dp[i - 1][ j ] , dp[i][j - 1]) ;
}
}
return dp[len1][len2];
}
int main()
{
while(cin >> str1 >> str2)
{
int len1 = strlen(str1) ;
int len2 = strlen(str2) ;
cout<<LCSL(len1 , len2)<<endl;
}
return 0;
}
Java 代碼
public class LCSProblem
{
public static void main(String[] args)
{
String[] x = {"", "A", "B", "C", "B", "D", "A", "B"};
String[] y = {"", "B", "D", "C", "A", "B", "A"};
int[][] b = getLength(x, y);
Display(b, x, x.length-1, y.length-1);
}
public static int[][] getLength(String[] x, String[] y)
{
int[][] b = new int[x.length][y.length];
int[][] c = new int[x.length][y.length];
for(int i=1; i<x.length; i++)
{
for(int j=1; j<y.length; j++)
{
if( x[i] == y[j])
{
c[i][j] = c[i-1][j-1] + 1;
b[i][j] = 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
b[i][j] = 0;
}
else
{
c[i][j] = c[i][j-1];
b[i][j] = -1;
}
}
}
return b;
}
public static void Display(int[][] b, String[] x, int i, int j)
{
if(i == 0 || j == 0)
return;
if(b[i][j] == 1)
{
Display(b, x, i-1, j-1);
System.out.print(x[i] + " ");
}
else if(b[i][j] == 0)
{
Display(b, x, i-1, j);
}
else if(b[i][j] == -1)
{
Display(b, x, i, j-1);
}
}
}
