LCS:又称最长公共子序列。其中子序列(subsequence)的概念不同于串的子串。它是一个不一定连续但按顺序取自字符串X中的字符序列。例如:串"AAAG"就是串“CGATAATTGAGA”的一个子序列。
字符串的相似性问题可以通过求解两个串间的最长公共子序列(LCS)来得到。当然如果使用穷举算法列出串的所有子序列,一共有2^n种,而每个子序列是否是另外一个串的子序列又需要O(m)的时间复杂度,因此这个穷举的方法时间复杂度是O(m*(2^n))指数级别,效率相当的可怕。我们采用动态规划算法来解决这个问题。
动态规划算法解决最长公共子序列
假如我们有两个字符串:X=[0,1,2....n] Y=[0,1,2...m]。我们定义L(i, j)为X[0...i]与Y[0...j]之间的最长公共子序列的长度。通过动态规划思想(复杂问题的最优解是子问题的最优解和子问题的重叠性质决定的)。我们考虑这样两种情况:
(1) 当X[i]=Y[j]时, L(i, j)=L(i-1, j-1)+1。证明很简单。
(2) 当X[i]!=Y[j]时,说明此事X[0...i]和Y[0...j]的最长公共子序列中绝对不可能同时含有X[i]和Y[j]。那么公共子序列可能以X[i]结尾,可能以Y[j]结尾,可以末尾都不含有X[i]或Y[j]。因此
L(i, j)= MAX{L(i-1 , j), L(i, j-1)}
LCS动态规划Java源代码
- package net.hr.algorithm.string;
-
-
-
-
- public class LCS {
-
- private char[] charArrayX=null;
-
- private char[] charArrayY=null;
- public LCS(String sa,String sb){
- charArrayX=new char[sa.length()+1];
- System.arraycopy(sa.toCharArray(),0,charArrayX,1,sa.length());
- charArrayY=new char[sb.length()+1];
- System.arraycopy(sb.toCharArray(),0,charArrayY,1,sb.length());
- }
-
-
-
- public void getLCS(){
- int[][] length=new int[charArrayX.length+1][charArrayY.length+1];
- for(int m=1;m<charArrayX.length;m++)
- for(int n=1;n<charArrayY.length;n++){
- if(charArrayX[m]==charArrayY[n]){
- length[m][n]=length[m-1][n-1]+1;
- }
- else
- length[m][n]=max(length[m-1][n],length[m][n-1]);
- }
-
- String lcstr="";
- int x=charArrayX.length-1;
- int y=charArrayY.length-1;
- while(x>=1&&y>=1){
- if(charArrayX[x]==charArrayY[y]){
- lcstr=charArrayX[x]+lcstr;
- x--;
- y--;
- }else{
- if(length[x-1][y]<=length[x][y-1])
- y--;
- else
- x--;
- }
- }
- System.out.println("最长公共子序列为:"+lcstr+" [length="+lcstr.length()+"]");
- }
-
-
-
- private int max(int m,int n){
- return m>n?m:n;
- }
-
-
-
- public static void main(String[] args) {
- LCS lcs=new LCS("GTTCCTAATA","CGATAATTGAGA");
- lcs.getLCS();
- }
- }
package net.hr.algorithm.string;
/**
* 最长公共子串LCS
* @author heartraid
*/
public class LCS {
/**字符串X的字符数组*/
private char[] charArrayX=null;
/**字符串Y的字符数组*/
private char[] charArrayY=null;
public LCS(String sa,String sb){
charArrayX=new char[sa.length()+1];
System.arraycopy(sa.toCharArray(),0,charArrayX,1,sa.length());
charArrayY=new char[sb.length()+1];
System.arraycopy(sb.toCharArray(),0,charArrayY,1,sb.length());
}
/**
* 得到最长公共子序列的长度
*/
public void getLCS(){
int[][] length=new int[charArrayX.length+1][charArrayY.length+1];
for(int m=1;m<charArrayX.length;m++)
for(int n=1;n<charArrayY.length;n++){
if(charArrayX[m]==charArrayY[n]){
length[m][n]=length[m-1][n-1]+1;
}
else
length[m][n]=max(length[m-1][n],length[m][n-1]);
}
//打印最长公共子序列
String lcstr="";
int x=charArrayX.length-1;
int y=charArrayY.length-1;
while(x>=1&&y>=1){
if(charArrayX[x]==charArrayY[y]){
lcstr=charArrayX[x]+lcstr;
x--;
y--;
}else{
if(length[x-1][y]<=length[x][y-1])
y--;
else
x--;
}
}
System.out.println("最长公共子序列为:"+lcstr+" [length="+lcstr.length()+"]");
}
/**
* 取最大值
*/
private int max(int m,int n){
return m>n?m:n;
}
/**
* 测试
*/
public static void main(String[] args) {
LCS lcs=new LCS("GTTCCTAATA","CGATAATTGAGA");
lcs.getLCS();
}
}
这里解释一下上面的代码,其中getLength()的作用是递归获取最长公共子串的长度,并得到递归过程中每个子串之间最长公共子串长度的状态表lcs[][],这张表运行的结果如下:
C G A T A A T T G A G A
0 0 0 0 0 0 0 0 0 0 0 0 0 G 0 0 1 1 1 1 1 1 1 1 1 1 1 T 0 0 1 1 2 2 2 2 2 2 2 2 2 T 0 0 1 1 2 2 2 3 3 3 3 3 3 C 0 1 1 1 2 2 2 3 3 3 3 3 3 C 0 1 1 1 2 2 2 3 3 3 3 3 3 T 0 1 1 1 2 2 2 3 4 4 4 4 4 A 0 1 1 2 2 3 3 3 4 4 5 5 5 A 0 1 1 2 2 3 4 4 4 4 5 5 6 T 0 1 1 2 3 3 4 5 5 5 5 5 6 A 0 1 1 2 3 4 4 5 5 5 6 6 6
红色数字的位置就揭示了最长公共子序列: CTATTA。也就是说分析这张表就可以得到最长公共子序列字符串。
为什么呢?因为通过表的回溯过程,从后向前重构了一个最长公共子序列。对于任何位置lcs[i][j],确定是否X[i]=Y[j]。如果是,那么X[i]必是最长公共子序列的一个字符。如果否,那么移动到lcs[i,j-1]和lcs[i-1, j]之间的较大者。
动态规划方法LCS效率:
动态规划方法构造最长公共子序列需要O(m*n)的代价,另外,如果想要得到最长公共子序列,又需要O(m+n)的时间来读取csl[][]数组。尽管如此,其时间复杂度仍然比蛮力穷举的指数级别要强的多。
问题拓展:设A,B,C是三个长为n的字符串,它们取自同一常数大小的字母表。设计一个找出三个串的最长公共子串的O(n^3)的时间算法。(来自《Algorithm Design》(中文版:算法分析与设计) - Chapter9 - 文本处理 - 创新题C-9.18)
分析:可以通过《LCS最长公共子序列》的动态规划算法,设计Java源代码如下:
- public class TriLCS{
- char[] charA=null;
- char[] charB=null;
- char[] charC=null;
- public TriLCS(String sa,String sb,String sc){
- charA=new char[sa.length()+1];
- System.arraycopy(sa.toCharArray(),0,charA,1,sa.length());
- charB=new char[sb.length()+1];
- System.arraycopy(sb.toCharArray(),0,charB,1,sb.length());
- charC=new char[sc.length()+1];
- System.arraycopy(sc.toCharArray(),0,charC,1,sc.length());
- }
- public void getTriLCS(){
- int[][][] length=new int[charA.length][charB.length][charC.length];
- for(int a=1;a<charA.length;a++)
- for(int b=1;b<charB.length;b++)
- for(int c=1;c<charC.length;c++){
- if(charA[a]==charB[b]&&charA[a]==charC[c]){
- length[a][b][c]=length[a-1][b-1][c-1]+1;
- }
- else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
- length[a][b][c]=max(length[a-1][b-1][c],length[a][b][c-1]);
- }
- else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
- length[a][b][c]=max(length[a-1][b][c-1],length[a][b-1][c]);
- }
- else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
- length[a][b][c]=max(length[a][b-1][c-1],length[a-1][b][c]);
- }
- else{
- length[a][b][c]=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
- }
- }
-
- String lcstr="";
- int a=charA.length-1;
- int b=charB.length-1;
- int c=charC.length-1;
- while(a>=1&&b>=1&&c>=1){
- if(charA[a]==charB[b]&&charA[a]==charC[c]){
- lcstr=charA[a]+lcstr;
- a--;
- b--;
- c--;
- }
- else if(charA[a]==charB[b]&&charA[a]!=charC[c]){
- if(length[a-1][b-1][c]<=length[a][b][c-1])
- c--;
- else{
- a--;
- b--;
- }
- }
- else if(charA[a]==charC[c]&&charA[a]!=charB[b]){
- if(length[a-1][b][c-1]<=length[a][b-1][c])
- b--;
- else{
- a--;
- c--;
- }
- }
- else if(charB[b]==charC[c]&&charA[a]!=charB[b]){
- if(length[a][b-1][c-1]<=length[a-1][b][c])
- a--;
- else{
- b--;
- c--;
- }
- }
- else{
- int maxize=max(length[a-1][b][c],length[a][b-1][c],length[a][b][c-1],length[a-1][b-1][c],length[a-1][b][c-1],length[a][b-1][c-1]);
- if(maxize==length[a-1][b][c])
- a--;
- if(maxize==length[a][b-1][c])
- b--;
- if(maxize==length[a][b][c-1])
- c--;
- if(maxize==length[a-1][b-1][c]){
- a--;
- b--;
- }
- if(maxize==length[a-1][b][c-1]){
- a--;
- c--;
- }
- if(maxize==length[a][b-1][c-1]){
- b--;
- c--;
- }
- }
- }
- System.out.println("最长子串为:"+lcstr+"(length="+length[charA.length-1][charB.length-1][charC.length-1]+")");
- }
-
-
-
- private int max(int m,int n){
- return m>n?m:n;
- }
-
-
-
- private int max(int x,int y,int z,int k,int m,int n){
- int maxizen=0;
- if(maxizen<x) maxizen=x;
- if(maxizen<y) maxizen=y;
- if(maxizen<z) maxizen=z;
- if(maxizen<k) maxizen=k;
- if(maxizen<m) maxizen=m;
- if(maxizen<n) maxizen=n;
- return maxizen;
- }
- public static void main(String[] args){
- TriLCS tri=new TriLCS("aadsbbbcs","adsabcs","adbsbsdcs");
- tri.getTriLCS();
- }
- }
|