如果有字符串X，Y 用c[i][j]表示Xi和Yi的最大公共子串長度
那么狀態(tài)轉移方程是
c[i][j]=c[i-1][j-1]+1 if xi=yi
c[i][j]=0 if xi!=yi
最后求Longest Common Substring的長度等于
max{ c[i][j], 1<=i<=n寇蚊， 1<=j<=m}
public static String getLCSLength(String s,String t){
int p = s.length() ;
int q = t.length();
String[][] num = new String[p][q];
char char1 = '\0';
char char2 = '\0' ;
int len = 0 ;
String lcs = "";
for(int i = 0;i<p ;i++){
for(int j=0;j<q;j++){
char1 = s.charAt(i);
char2 = t.charAt(j);
if(char1 != char2){
num[i][j] = "";
}
else {
if(i==0 ) num[i][j] = String.valueOf(char1) ;
else if(j ==0)num[i][j] = String.valueOf(char2);
else num[i][j] = num[i-1][j-1] +String.valueOf(char1) ;
if(num[i][j].length() > len){
len = num[i][j].length();
lcs = num[i][j];
}
else if(num[i][j].length() == len){
lcs = lcs +","+num[i][j] ;
}
}
}
}
return lcs ;
}
