最长公共子序列问题LCS Longest Common Subsequence

2023-12-07 13 0

动态规划求最长公共子序列(LCS  Longest Common Subsequence)

最长公共子序列问题:
给定两个序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn },找出 X 和 Y 的最长公共子序列。
一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列 X 和 Y ,当另一序列 Z 既是 X 的子序列又是 Y 的子序
列时,称 Z 是序列 X 和 Y 的公共子序列。
例如,若 X = {A, B, C, B, D, A, B },
             Y = {B, D, C, A, B, A },
序列{B, C, A }是 X 和 Y 的一个公共子序列,序列{B, C, B, A }也是 X 和 Y 的一个公共子序列,且为最长公共子序列。

最长公共子序列问题具有最优子结构性质。
设序列 X = {x1, x2, ......, xm } 和 Y = {y1, y2, ......, yn }的最长公共子序列为 Z = {z1, z2, ......, zk}
则(1) 若 xm = yn ,则 zk = xm = yn ,且 Zk-1 是 Xm-1 和 Yn-1 的最长公共子序列
   (2) 若 xm != yn 且 zk != xm ,则 Z 是 Xm-1 和 Y 的最长公共子序列。
   (3) 若 xm != yn 且 zk != yn ,则 Z 是 X 和 Yn-1 的最长公共子序列。
其中:
Xm-1 = {x1, x2, ......, xm-1 }; Yn-1 = {y1, y2, ......, yn-1}; Zk-1 = {z1, z2, ......, zk-1}。
    引进一个二维数组C,用C[i,j]记录X与Y的LCS的长度,如果我们是自底向上进行递推计算,

那么在计算C[i,j]之前,C[i-1,j-1], C[i-1,j]与C[i,j-1]均已计算出来。

此时我们根据X[i]=Y[j]还是X[i]≠Y[j],就可以计算出C[i,j]:

若X[i]=Y[j],则执行C[i,j]=C[i-1,j-1]+1;

若X[i]≠Y[j],则根据:C[i-1,j]≥C[i,j-1],则C[i,j]取C[i-1,j];

否则C[i,j]取C[i,j-1]。 //即:表示去c[i][j-1],c[i-1][j]中的其中的最大值。

    为了构造出LCS,使用一个m×n的二维数组b,

 b[i,j]记录C[i,j]是通过哪一个子问题的值求得的,以决定搜索的方向:
若C[i-1,j]≥C[i,j-1],则b[i,j]中记入“0”;
若C[i-1,j] < C[i,j-1],则b[i,j]中记入“-1”;

import java.util.Stack;
import java.util.Random;
public class LCSProblem    
{   private char[] x; //private char[] y;int b[][];int c[][];//C[i,j]记录X与Y的LCS的长度public LCSProblem(String s1,String s2){    x=new String(" "+s1).toCharArray();  //空串是为了让后面没有越界错误,因为后面的循环式从第一个开始的y=new String(" "+s2).toCharArray();b=new int[x.length][y.length];c=new int[x.length][y.length];}public static void main(String[] args)   {   LCSProblem lcs=new LCSProblem("pjwrbilcerzypsedamgk","kqeddkogpazssnnr");lcs.getLength();   lcs.Display0();   System.out.println();lcs.Display1();System.out.println();// 随机生成字符串String ss = GetRandomStrings(9);String ss1 = GetRandomStrings(6);System.out.println("ss="+ss);System.out.println("ss1="+ss1);lcs=new LCSProblem(ss,ss1);lcs.getLength();   lcs.Display0();   System.out.println();lcs.Display1();}   private void getLength()   //计算c[i][j],从前往后计算{   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];    //c[i][j]取最大的值 b[i][j] = 0;   }   else  {   c[i][j] = c[i][j-1];   b[i][j] = -1;   }   }   }      }   public  void Display0(){//输出最长公共子序列int i = x.length-1, j = y.length-1;     //从最后的一个开始遍历.Stack< Character> sta=new Stack< Character>();while (i>=1&& j >=1){if (b[i][j]==1) {sta.push(x[i]);    //引进栈的目的是为了从最后的一个开始入栈,满足先进后出的原则i--;j--;} else if (b[i][j]==0)i--;elsej--;}while(!sta.empty())System.out.print(sta.pop()+" ");} public void Display1(){输出最长公共子序列Display2(x.length-1,y.length-1);}public  void Display2(int i, int j)  //递归求解 {   if(i == 0 || j == 0)   return;   if(b[i][j] == 1)     //为递归的终止条件{   Display2(i-1, j-1);   System.out.print(x[i] + " ");   }   else if(b[i][j] == 0)   {   Display2(i-1, j);   }   else if(b[i][j] == -1)   {   Display2(i, j-1);   }   }   }  

代码编程
赞赏

相关文章

微信CRM系统:微商不可或缺的客户管理利器!
android OTA 简介
android OTA差分包的生成方法
头条抖音后端技术3面,java零基础自学网
FrameBuffer相关
字节跳动算法工程师面试总结,头条抖音后端技术3面题:Linux