字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。
令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列，存在X的一个严格递增下标序列i=i0,i1,…,ik-1,使得对所有的j=0,1,…,k-1,有xi＝yj。
例如，X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
递归
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
| package com.example.demo;
public class Test8 {
static String[] a = {"A", "B", "C", "B", "D", "A", "B"};
static String[] b = {"B", "D", "C", "A", "B", "A"};
static int n = a.length;
static int m = b.length;
static String[] str = new String[n];
static int[][] dp = new int[n + 1][m + 1];
public static void main(String[] args) {
int k = lcs_len(n, m);
build_lcs(k, n, m);
for (String s : str) {
System.out.println(s);
}
}
static int lcs_len(int i, int j) {
int t1, t2;
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else if (a[i - 1].equals(b[j - 1])) {
dp[i][j] = lcs_len(i - 1, j - 1) + 1;
} else {
t1 = lcs_len(i, j - 1);
t2 = lcs_len(i - 1, j);
dp[i][j] = Math.max(t1, t2);
}
return dp[i][j];
}
static void build_lcs(int k, int i, int j) {
if (i == 0 || j == 0) {
return;
}
if (dp[i][j] == dp[i - 1][j]) {
build_lcs(k, i - 1, j);
} else if (dp[i][j] == dp[i][j - 1]) {
build_lcs(k, i, j - 1);
} else {
str[k] = a[i - 1];
build_lcs(k - 1, i - 1, j - 1);
}
}
}
|
非递归
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
| package com.example.demo;
public class Test8 {
static String[] a = {"A", "B", "C", "B", "D", "A", "B"};
static String[] b = {"B", "D", "C", "A", "B", "A"};
static int n = a.length;
static int m = b.length;
static String[] str = new String[n];
static int[][] dp = new int[n + 1][m + 1];
public static void main(String[] args) {
int k = lcs_len();
build_lcs(k);
for (String s : str) {
System.out.println(s);
}
}
static void build_lcs(int k) {
int i = n;
int j = m;
while (k > 0) {
if (dp[i][j] == dp[i - 1][j]) {
i = i - 1;
} else if (dp[i][j] == dp[i][j - 1]) {
j = j - 1;
} else {
k = k - 1;
i = i - 1;
j = j - 1;
str[k] = a[i];
}
}
}
static int lcs_len() {
for (int i = 0; i <= n; i++)
dp[i][0] = 0;
for (int j = 0; j <= m; j++)
dp[0][j] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1].equals(b[j - 1])) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[a.length][b.length];
}
}
|
参考文章