查找最长公共子序列
什么是最长公共子序列？
一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
例： 如下有两个字符串： x：A B C B D A B y：B D C A B A 查找它们最长公共子序列。 则它们公共子序列有（B D A B）(B D A B) (B C B A)
如何进行查找\思路？
找最长公共子序列长度lcs(x,y) lcs(x[0],x[0])=0 lcs(x[1],x[1])=0 如果不相等为0 lcs(x[2],x[2])=0分情况： lcs(x[1],x[2])=0 lcs(x[2],x[1])=1 此时lcs(x[2],x[2])=1 即取两种情况的最大值 lcs(x[3],x[3])=2 lcs(x[4],x[4])=0分情况： lcs(x[3],x[4])=2 lcs(x[4],x[3])=2 此时lcs(x[4],x[4])=2 lcs(x[5],x[5])=0分情况： lcs(x[4],x[5)=3 lcs(x[5],x[4])=2 此时lcs(x[4],x[4])=3 。。。。。剩下的以此类推
伪代码如下： lcs（x,y,i,j）{ if(i0 or j0)return 0; else if(x[i]==x[j])return lcs(x,y,i,j)+1; else return max(lcs(x,y,i,j–),lcs(x,y,i-1,j)); }
key1:穷举法
穷举法需要遍历出所有的可能，在这不考虑。
key2: 递归方法
static int f(char[] a
, char[] b
, int i
, int j
) {
if (i
== 0 || j
== 0) {
return 0;
} else if (a
[i
] == b
[j
]) {
return f(a
, b
, i
- 1, j
- 1) + 1;
} else {
return Max(f(a
, b
, i
, j
- 1), f(a
, b
, i
- 1, j
));
}
}
static int Max(int a
, int b
) {
if (a
> b
)
return a
;
else
return b
;
}
public static void main(String
[] args
) {
String s1
= " abcdfadskb";
String s2
= " abefaslf";
char[] c1
= new char[s1
.length() + 1];
char[] c2
= new char[s1
.length() + 1];
char[] t1
= s1
.toCharArray();
char[] t2
= s1
.toCharArray();
c1
[0] = (char) 0;
c2
[0] = (char) 0;
for (int i
= 0; i
< t1
.length
; i
++) {
c1
[i
+ 1] = t1
[i
];
}
for (int i
= 0; i
< t2
.length
; i
++) {
c2
[i
+ 1] = t2
[i
];
}
System
.out
.println(f(s1
.toCharArray(), s2
.toCharArray(), 4, 4));
}
key3：备忘录法
static int f(char[] a
, char[] b
, int i
, int j
, int[][] bak
) {
if (bak
[i
][j
] != -1)
return bak
[i
][j
];
if (i
== 0 || j
== 0) {
bak
[i
][j
] = 0;
} else if (a
[i
] == b
[j
]) {
bak
[i
][j
] = f(a
, b
, i
- 1, j
- 1, bak
) + 1;
} else {
bak
[i
][j
] = Max(f(a
, b
, i
, j
- 1, bak
), f(a
, b
, i
- 1, j
, bak
));
}
return bak
[i
][j
];
}
static int Max(int a
, int b
) {
if (a
> b
)
return a
;
else
return b
;
}
public static void main(String
[] args
) {
String s1
= " ABCBDAB";
String s2
= " BDCABA";
char[] c1
= new char[s1
.length() + 1];
char[] c2
= new char[s2
.length() + 1];
char[] t1
= s1
.toCharArray();
char[] t2
= s1
.toCharArray();
c1
[0] = (char) 0;
c2
[0] = (char) 0;
for (int i
= 0; i
< t1
.length
; i
++) {
c1
[i
+ 1] = t1
[i
];
}
for (int i
= 0; i
< t2
.length
; i
++) {
c2
[i
+ 1] = t2
[i
];
}
int[][] bak
= new int[c1
.length
][c2
.length
];
for (int i
= 0; i
< c1
.length
; i
++) {
for (int j
= 0; j
< bak
[i
].length
; j
++) {
bak
[i
][j
] = -1;
}
}
System
.out
.println(f(c1
, c2
, c1
.length
- 1, c2
.length
- 1, bak
));
}
key4：自底向上
static int f(char[] a
, char[] b
, int i
, int j
, int[][] bak
) {
for(int ii
=0;ii
<=i
;ii
++) {
for(int jj
=0;jj
<=j
;jj
++) {
if (ii
== 0 || jj
== 0) {
bak
[ii
][jj
] = 0;
} else if (a
[ii
] == b
[jj
]) {
bak
[ii
][jj
] = bak
[ii
-1][jj
-1]+ 1;
} else {
bak
[ii
][jj
] = Max(bak
[ii
-1][jj
],bak
[ii
][jj
-1]);
}
}
}
return bak
[i
][j
];
}
static int Max(int a
, int b
) {
if (a
> b
)
return a
;
else
return b
;
}
public static void main(String
[] args
) {
String s1
= "ABCBDAB";
String s2
= "BDCABA";
char[] c1
=new StringBuffer((char)0).append(s1
).toString().toCharArray();
char[] c2
= new char[s2
.length() + 1];
char[] t2
= s2
.toCharArray();
c2
[0] = (char) 0;
for (int i
= 0; i
< t2
.length
; i
++) {
c2
[i
+ 1] = t2
[i
];
}
int[][] bak
= new int[c1
.length
][c2
.length
];
System
.out
.println(f(c1
, c2
, c1
.length
- 1, c2
.length
- 1, bak
));
}
