动态规划解最长公共子序列(LCS)_最长公共子序列实际应用 - wpsshop博客
devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

动态规划解最长公共子序列(LCS)_最长公共子序列实际应用

作者：笔触狂放9 | 2024-02-15 21:58:38

赞

踩

最长公共子序列实际应用

举例：AOIDSAFKE和TGRARIDWQFKDA的最长公共子序列为AIDFK

设X=<x1,x2,x3,x4…,xm>，Y=<y1,y2,y3,y4…,yn>为两个序列，Z=<z1,z2,z3,z4…,zk>是他们的任意公共子序列

经过分析，我们可以知道：

1、如果xm = yn，则zk = xm = yn 且 Zk-1是Xm-1和Yn-1的一个LCS

2、如果xm != yn 且 zk != xm，则Z是Xm-1和Y的一个LCS

3、如果xm != yn 且 zk != yn，则Z是X和Yn-1的一个LCS

所以如果用一个二维数组c表示字符串X和Y中对应的前i，前j个字符的LCS的长度话，可以得到以下公式：
在这里插入图片描述
设

p1表示X的前 i-1 个字符和Y的前 j 个字符的LCS的长度

p2表示X的前 i 个字符和Y的前 j-1 个字符的LCS的长度

p表示X的前 i-1 个字符和Y的前 j-1 个字符的LCS的长度

p0表示X的前 i 个字符和Y的前 j 个字符的LCS的长度

如果X的第 i 个字符和Y的第 j 个字符相等，则p0 = p + 1

如果X的第 i 个字符和Y的第 j 个字符不相等，则p0 = max(p1,p2)

在对应字符相等的时候，用↖标记

在p1 >= p2的时候，用↑标记

在p1 < p2的时候，用←标记
在这里插入图片描述
代码：

public class LCSLength {
	static String path;	//最长公共子序列
	public static void main(String[] args) {
		String x = "AOIDSAFKE";
		String y = "TGRARIDWQFKDA";
		int[][] matrix = new int[x.length()+1][y.length()+1];
		int[][] direction = new int[x.length()+1][y.length()+1];	//0表示左上箭头，1表示上箭头，-1表示左箭头
		for (int i = 1; i < matrix.length; i++) {
			for (int j = 1; j < matrix[0].length; j++) {
				if(x.charAt(i-1)==y.charAt(j-1)){
					matrix[i][j] = matrix[i-1][j-1]+1;
					direction[i][j] = 0;
				}else{
					if(matrix[i][j-1]>=matrix[i-1][j]){
						matrix[i][j] = matrix[i][j-1];
						direction[i][j] = -1;
					}else{
						matrix[i][j] = matrix[i-1][j];
						direction[i][j] = 0;
					}
				}
			}
		}
//		for (int i = 0; i < matrix.length; i++) {
//			for (int j = 0; j < matrix[0].length; j++) {
//				System.out.print(direction[i][j]+"\t");
//			}
//			System.out.println();
//		}
		printPath(y,direction,x.length()-1,y.length()-1);
		System.out.println(path);
	}

	private static void printPath(String y,int[][] direction,int i,int j) {	//根据direction找最长公共子序列
		if(i>=1&&j>=1){
			if(direction[i][j] == 0){
				if(path == null){
					path = String.valueOf(y.charAt(j-1));
				}else{
					path = String.valueOf(y.charAt(j-1))+path;
				}
				printPath(y,direction,i-1,j-1);
			}else if(direction[i][j] == 1){
				printPath(y,direction,i-1,j);
			}else{
				printPath(y,direction,i,j-1);
			}
		}else{
			return;
		}
	}
}



  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/87373
推荐阅读
相关标签