最长公共子序列（Java）——输出全部！！！_两个字符串最长公共子序列并打印java

一、问题提出：

给定两个字符串，寻找这两个字符串之间的最长公共自子序列（给出全部）

二、含义：

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。

一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切的说，若给定序列X={x1，x2，…，xm}，则另一序列Z={z1，z2，…，zk}，X的子序列是指存在一个严格的递增下标序列{i1，i2，…，ik}使得对所有的j=1,2，…，k有zj=xij。例如：序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}，相应的递增下标序列为{2,3，5,7}。

三、举例：

若X={A，B，C，B，D，A，B}，Y={B，D，C, A，B，A}；

1. 公共子序列：
   序列{B，C，A}
   为公共子序列，并不是X和Y的最长公共子序列
2. 最长公共子序列：
   序列{B，C，B，A}
   为最长共公共子序列

可以看出，最长公共子序列并不唯一！！！

四、步骤设计（最优子结构性质）：

1.最长公共子序列的结构
最长公共子序列问题具有最优子结构性质。
设序列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}
.
2. 子问题的递归结构
递归计算求得最长公共子序列：
（1）当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm（=yn）即可得到X和Y的最长公共子序列。
（2）当xm！=yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列以及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长的即为X和Y的最长公共子序列。

建立子问题最优值的递归关系：

3. 计算最优值

public static int lcsLength(char []x,char []y,int [][]b){
	//c[i][j]存储Xi和Yj的最长公共子序列的长度；
	//b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的。
	//c[m][n]，问题的最优值，即X和Y的最长公共子序列的长度。
	
	int m=x.length-1;
	int n=y.length-1;
	int [][]c=new int [m+1][n+1];
	for(int i=1;i<=m;i++){
		c[i][0]=0;
	}
	for(int i=1;i<=n;i++){
		c[0][i]=0;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;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]=2;
			}else{
				c[i][j]=c[i][j-1];
				b[i][j]=3;
			}
		}
	}
	return c[m][n];
}
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

4.构造最长公共子序列
由算法lcsLength计算得到的数组b可用于快速构造序列X和Y的最长公共子序列。
（1）当b[i][j]==1时，表示Xi和Yj的最长公共子序列是由Xi-1和Yj-1的最长公共子序列在尾部加上xi所得到的子序列；
（2）当b[i][j]==2时，表示Xi和Yj的最长公共子序列与Xi-1和Yj的最长公共子序列相同；
（3）当b[i][j]==3时，表示Xi和Yi的最长公共子序列与Xi和Yj-1的最长公共子序列相同。

算法lcs实现根据b的内容打印Xi和Yj的最长公共子序列。

public static void lcs(int i,int j,char []x,int [][]b){
	if(i==0||j==0)
		return;
	if(b[i][j]==1){
		lcs(i-1,j-1,x,b);
		System.out.print(x[i]);
	}else if(b[i][j]==2){
		lcs(i-1,j,x,b);
	}else{
		lcs(i,j-1,x,b);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

五、完整代码

package com.jiyongfei.lcs2;

import java.util.Scanner;
import java.util.TreeSet;

/**
 * 
 * @Description 最长公共子序列
 * @author jiyongfei Email:2384074837@qq.com
 * @version
 * @date 2020年6月22日下午9:39:07
 *
 */
public class LongestLcs {
	public StringBuffer X;
	public StringBuffer Y;

	public static int m;
	public static int n;

	public static int[][] b;
	public int[][] c;

	public int len;
	public String[] Log;
	public final int MAX = 100;
	public char[] lcs;
	public int CurLen;

	public static void main(String[] args) {
		LongestLcs lcs = new LongestLcs();
		lcs.search();
	}

	public void search() {
		while (true) {
			System.out.println("\n" + "请选择功能:");
			System.out.println("\n" + "1.寻找最长公共子序列");
			System.out.println("\n" + "2.结束.");

			Scanner in = new Scanner(System.in);
			int choose = in.nextInt();

			switch (choose) {
			case 1:
				System.out.println("请输入序列X:");
				X = new StringBuffer(in.next());
				System.out.println("请输入序列Y:");
				Y = new StringBuffer(in.next());

				lcs_length();
				System.out.println("两序列的最长公共子序列为:");
				StoreLCS(m, n, len);
				PrintLCS();
				X.setLength(0);
				Y.setLength(0);
				break;

			case 2:
				in.close();
				System.exit(0);
				break;

			default:
				in.close();
				System.exit(-1);
			}

		}
	}

	/**
	 * 
	 * @Description 计算最优值 
	 * c[i][j]存储Xi和Yj的最长公共子序列的长度 
	 * b[i][j]记录c[i][j]的值是由哪一个子问题的解得到的
	 * len=c[m][n],问题的最优值，即XY的最长公共子序列的长度
	 * @author jiyongfei
	 * @date 2020年6月23日上午7:51:09
	 */
	public void lcs_length() {
		m = X.length();
		n = Y.length();
		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;
				}
			}
		}
		lcs = new char[m + 1];
		len = c[m][n];
		Log = new String[MAX];
		CurLen = 0;

	}
	/**
	 * 
	 * @Description 根据b的内容，存储Xi和Yi的最长公共子序列
	 * @author jiyongfei
	 * @date 2020年6月23日上午8:09:01
	 * @param m
	 * @param n
	 * @param Len
	 */
	public void StoreLCS(int m, int n, int Len) {
		if (m == 0 || n == 0) {
			Log[CurLen] = new String(lcs);
			CurLen++;
		} else {
			if (b[m][n] == 0) {
				lcs[Len] = X.charAt(m - 1);
				Len--;
				StoreLCS(m - 1, n - 1, Len);
			} else if (b[m][n] == 1) {
				StoreLCS(m - 1, n, Len);
			} else if (b[m][n] == 2) {
				StoreLCS(m, n - 1, Len);
				StoreLCS(m - 1, n, Len);
			} else {
				StoreLCS(m, n - 1, Len);

			}
		}

	}
	
	/**
	 * 
	 * @Description 算法PrintLCS打印最长公共子序列
	 * @author jiyongfei
	 * @date 2020年6月23日上午8:09:51
	 */
	public void PrintLCS() {
		TreeSet<String> tr = new TreeSet<String>();// 树集合定义
		for (int i = 0; i < CurLen; i++) {
			tr.add(Log[i]);
		}
		String[] s2 = new String[tr.size()];
		for (int i = 0; i < s2.length; i++) {
			s2[i] = tr.pollFirst(); // 返回并删除最低元素
			System.out.println(s2[i]);
		}
	}
}

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165