最长公共子序列与最长连续公共子序列-Java-蒲公英云

最长公共子序列与最长连续公共子序列-Java

最长公共子序列与最长连续公共子序列（java）

1、最长公共子序列，顺序是一致并且相等，但是字符之间可以不是连续的。

2、求最长公共字符串，这就要求既是公共的字符串，又需要是连续的。

package pratice725;
//最长公共子序列与最长连续公共子序列（java）
//顺序是一致并且相等，但是字符之间可以不是连续的。
public class findLCS {
public static void findLCS(String str,String patt){
int strl = str.length();
int pattl = patt.length();
int lcs[][] = new int[strl][pattl];
char strc[] = str.toCharArray();
char pattc[] = patt.toCharArray();
if(str==null || strl==0 || patt==null || pattl==0) return;
int t = 0;
for(int i =0;i<strl;i++){
if(strc[i]==pattc[0])
{
t = 1;
}
lcs[i][0]=t;
}
t = 0;
for(int j=0;j<pattl;j++){
if(strc[0]==pattc[j]){
t = 1;
}
lcs[0][j] = t;
}
for(int i=1;i<strl;i++){
for(int j=1;j<pattl;j++)
{
if(strc[i]==pattc[j]){
lcs[i][j] = lcs[i-1][j-1]+1;
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
System.out.println(“最大公共子序列长度矩阵是： “);
for(int i=0;i<strl;i++){
for(int j=0;j<pattl;j++)
{
System.out.print(lcs[i][j]+” “);
}
System.out.println(“”);
}
System.out.println(“最大公共子序列长度是： “+lcs[strl-1][pattl-1]);
}
//求最长公共字符串，这就要求既是公共的字符串，又需要是连续的。
public static void getLCSString(String str,String patt){
int strl = str.length();
int pattl = patt.length();
int lcs[][] = new int[strl][pattl];
char strc[] = str.toCharArray();
char pattc[] = patt.toCharArray();
if(str==null || strl==0 || patt==null || pattl==0) return;
int t = 0;
for(int i =0;i<strl;i++){
if(strc[i]==pattc[0])
{
t = 1;
}else{
t=0;
}
lcs[i][0]=t;
}
t = 0;
for(int j=0;j<pattl;j++){
if(strc[0]==pattc[j]){
t = 1;
}else{
t=0;
}
lcs[0][j] = t;
}
for(int i=1;i<strl;i++){
for(int j=1;j<pattl;j++)
{
if(strc[i]==pattc[j]){
lcs[i][j] = lcs[i-1][j-1]+1;
}else{
lcs[i][j] = 0;
}
}
}
System.out.println(“最大公共子串矩阵是： “);
for(int i=0;i<strl;i++){
for(int j=0;j<pattl;j++)
{
System.out.print(lcs[i][j]+” “);
}
System.out.println(“”);
}
}
public static void main(String[] args) {
String str = “android”;
String patt = “random”;
findLCS(str,patt);
System.out.println(“”);
getLCSString(str,patt);
}
}