我的第一篇博客----LCS学习笔记

时间:2022-04-04 17:43:55

LCS引论

在这篇博文中,博主要给大家讲一个算法----最长公共子序列(LCS)算法。我最初接触这个算法是在高中学信息学竞赛的时候。那时候花了好长时间理解这个算法。老师经常说,这种算法是母算法,即从这种算法中能衍生出许许多多的子算法。是的,博主在大二的算法导论考试中,就被LCS衍生的子算法“坑”了。当时一道动态规划题目,大概是要写一列书中放置书架的问题。博主联想到了LCS,但是最后还是只是用暴力求解法解出了那道题目,甚是遗憾。在这里,我也对此算法做一个详解。

优化子结构

首先,我们来看优化子结构:

设X=(x 1 , ..., x m ) 、Y=(y 1 , ..., y n )  是两个序列,Z=(z 1 , ..., z k ) 是X 与Y 的LCS ,我们有:

⑴     如果xm =yn,  则zk =xm = yn , Zk-1 是Xm-1 和Yn-1 的LCS , 即 :

LCS XY  = LCS X m-1 Y n-1 + <xm =yn >.

⑵     如果xm ≠ yn , 且zk≠ xm , 则Z 是X m-1 和Y 的

LCS , 即  LCS XY = LCS X m-1 Y

⑶     如果xm ≠ yn ,且zk≠ yn ,则Z 是X 与Y n-1 的LCS ,即 :

LCS XY = LCS XY n-1

构造C[m,n]数组表示xm 、yn 的LCS长度,因此,求得X和Y的优化解结构的递归方程为:

C[i, j] = 0 if i=0  或 j=0

C[i, j] = C[i-1, j-1] + 1 if i, j>0  且 x i  = y j

C[i, j] = Max(C[i, j-1], C[i-1, j]) if i, j>0  且 x i ≠ y j

在存储LCS的时候,我们根据已经构造好的B[m,n]来寻找全部的LCS。

如果B[m,n]=0,说明X和Y当前比对的字符相同,因此我们把X和Y都向前一个字符,再进行比对。

如果B[m,n]=1,说明xm ≠ yn , 且zk≠ xm ,此时我们只用把X向前移一位,再进行比对。

如果B[m,n]=3,说明xm ≠ yn ,且zk≠ yn,此时我们需要把Y向前移动一位,再进行比对。

如果B[m,n]=2,说明c[i - 1][j] = c[i][j - 1],我们需要将两个字符串依次向前移动一位,进行比对

关键的数据结构及简单说明

C[m,n]: C[i,j] 是X i 与Y j 的LCS 的长度;

B[m,n]: B[i,j] 是指针 ,指向计算C[i,j] 时所选择的子问题的优化解所对应的C 表的表项。通俗的说,B[m,n]记录的是轨迹;

public static String[] Log:存储全部LCS字符串;

public static char[] lcs:字符数组,存储

TreeSet<String> tree = new TreeSet<String>():将LCS数组存入Tree集合中,供打印使用。

示例程序

 package test;

import java.util.Scanner;

import java.util.TreeSet;

public class LCS {

public static StringBuffer X;

public static StringBuffer Y;

public static int m;

public static int n;

public static int len;

public static int[][] b;

public static int[][] c;

public static String[] Log;

public static char[] lcs;

public final static int MAX = 100;

public static int boardlen;

public static void main(String[] args) {

Log = new String[MAX];

LCS lcs = new LCS();

Scanner in = new Scanner(System.in);

System.out.println("string X:");

X = new StringBuffer(in.next());

System.out.println("string Y:");

Y = new StringBuffer(in.next());

lcs_length();

System.out.println("LCS:");

store_lcs(m, n, len);

PrintLCS();

X.setLength(0);

Y.setLength(0);

in.close();

}

public static void lcs_length() {

m = X.length();

n = Y.length();

lcs = new char[m + 1];

boardlen = 0;

c = new int[m + 1][n + 1];

b = new int[m + 1][n + 1];

for (int i = 1; i <= m; i++)

c[i][0] = 0;

for (int j = 0; j <= n; j++)

c[0][j] = 0;

for (int i = 1; i <= m; i++){

for (int j = 1; j <= n; j++) {

if (X.charAt(i - 1) == Y.charAt(j - 1)) {

c[i][j] = c[i - 1][j - 1] + 1;

b[i][j] = 0;

} else if (c[i - 1][j] > c[i][j - 1]) {

c[i][j] = c[i - 1][j];

b[i][j] = 1;

} else if (c[i - 1][j] == c[i][j - 1]) {

c[i][j] = c[i - 1][j];

b[i][j] = 2;

} else {

c[i][j] = c[i][j - 1];

b[i][j] = 3;

}

}

}

len = c[m][n];

}

public static void store_lcs(int m, int n, int Len) {

if (m == 0 || n == 0) {

Log[boardlen] = new String(lcs);

boardlen++;

} else {

if (b[m][n] == 0) {

lcs[Len] = X.charAt(m - 1);

Len--;

store_lcs(m - 1, n - 1, Len);

} else if (b[m][n] == 3) {

store_lcs(m, n - 1, Len);

} else if (b[m][n] == 1) {

store_lcs(m - 1, n, Len);

} else {

store_lcs(m, n - 1, Len);

store_lcs(m - 1, n, Len);

}

}

}

public static void PrintLCS() {

TreeSet<String> tree = new TreeSet<String>();

for (int i = 0; i <boardlen; i++) {

tree.add(Log[i]);

}

String[] string = new String[tree.size()];

for (int i = 0; i < string.length; i++) {

string[i] = tree.pollFirst();

System.out.println(string[i]);

}

}

public void printit() {

for (int i = 0; i < Log.length; i++) {

if (Log[i] != null) {

System.out.println(Log[i]);

}

}

}

}

后序

程序经本人测试,能够运行出正确结果。以上仅供大家学习交流,转载请注明出处。