第十周：最长公共子串问题

理解：
假设：
子串a = “GDVEGDA” 和子串b = “GVCEKST” ，
a[1]…a[i] 和 b[1]…b[j]
第一种情况：a[i] 不等于 b [j]
最长的公共子列为：
a[1] … a[i] 和 b[1]…b[j-1]或者 a[1] … a[i-1] 和 b[1]…b[j]
所以
c[i][j] = max{a[1] … a[i] 和 b[1]…b[j-1], a[1] … a[i-1] 和 b[1]…b[j]}
第二种情况：a[i] 等于 b [j]
在a[1][i-1]…b[1][j-1]里找公共子列
然后 最长的公共子列为 c[i-1][j-1] + 1
代码：
import java.util.Scanner;

public class LongCharacter {
public static void main(String[] args) {
//a：第一串；b:第二串；
Scanner input = new Scanner(System.in);
System.out.print(“输入字符串1：”);
String a = input.next();
System.out.print(“输入字符串2：”);
String b = input.next();
char[] aa = a.toCharArray();
char[] bb = b.toCharArray();
int m = aa.length;
int n = bb.length;
//初始化边界
int[][] table = new int[m+1][n+1];
for (int i = 0 ; i < table.length; i++) {
table[0][i] =0;
}
for (int i = 0 ; i < table.length; i++) {
table[i][0] =0;
}
for (int i = 1; i <= m ; i++) {
for (int j = 1; j <= n ; j++) {
if ( aa[i-1] == bb[j-1]){
table[i][j] = table[i-1][j-1] + 1;
}
else {
if (table[i][j-1] >= table[i-1][j])
{
table[i][j] = table[i][j-1];
}
else
{
table[i][j] = table[i-1][j];
}
}
}
}
System.out.println(“第一串：” + a);
System.out.println(“第一串：” + b);
for (int i = 0; i <= m ; i++) {
for (int j = 0; j <= n ; j++) {
System.out.print(table[i][j]+" ");
}
System.out.println();
}
System.out.println(“最长公共子列为：”);
int x=1;
for (int i = 0; i < m ; i++) {
if (table[i][m] == x){
System.out.print(aa[i-1]);
x++;
}
}
}
}

运行结果：