Source code:
package dynamic;
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println("Program is running ...");
Solution s=longestSequence("abbaab","aabaabb");
for (int i=0;i<=s.m1;i++){
for (int j=0;j<=s.n1;j++){
System.out.print(s.c[i][j]+" ");
}
System.out.println();
}
System.out.println("The solution matrix b is");
String str;
for (int i=0;i<=s.m1;i++){
for (int j=0;j<=s.n1;j++){
if(s.b[i][j]=='a'){
System.out.print("up"+"\t");
}
if(s.b[i][j]=='u'){
System.out.print("upleft "+"\t");
}
if(s.b[i][j]=='l'){
System.out.print("left"+"\t");
}
}
System.out.println();
}
}
public static Solution longestSequence (String x,String y){
int m=x.length();
int n=y.length();
/*
* solution matrix b
* in whic u=upleft
* a=up
* and l=left
*/
Solution s=new Solution(m,n);
for(int i=1;i<=m;i++) s.c[i][0]=0;
for(int j=0;j<=n;j++) s.c[0][j]=0;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++){
if(x.charAt(i-1)==y.charAt(j-1)){
s.c[i][j]=s.c[i-1][j-1]+1;
s.b[i][j]='u';
}
else if(s.c[i-1][j]>s.c[i][j-1]){
s.c[i][j]=s.c[i-1][j];
s.b[i][j]='a';
}
else
{
s.c[i][j]=s.c[i][j-1];
s.b[i][j]='l';
}
}
}
return s;
}
}
package dynamic;
public class Solution {
public int [][]c;
public char [][]b;
public int m1,n1;
public Solution(int m1,int n1){
this.c=new int [m1+1][n1+1];
this.b=new char[m1+1][n1+1];
this.m1=m1;
this.n1=n1;
}
public Solution(){
}}
No comments:
Post a Comment