Code666 (代码贴、代码片段)

[Java] 动态规划之最长公共子序列Java实现 →→→→→进入此内容的聊天室

来自 , 2021-01-05, 写在 Java, 查看 133 次.
URL http://www.code666.cn/view/792dd774
  1. public class lcs {  
  2.  
  3.     /**
  4.      * @param args
  5.      */  
  6.     public static void main(String[] args) {  
  7.         String str1 = "ACCGGTCGAGTGCGCGGAAGCCGGCCGAA";  
  8.         String str2 = "GTCGTTCGGAATGCCGTTGCTCTGTAAA";  
  9.         int m = str1.length();  
  10.         int n = str2.length();  
  11.         int[][] c = new int[m+1][n+1];  
  12.         System.out.println("lcs长度为"+lcs_len(str1,str2,c));  
  13.         System.out.println("lcs序列为");  
  14.         print_lcs(str1,str2,c);  
  15.  
  16.     }  
  17.     public static int lcs_len(String str1,String str2,int[][] c){  
  18.         if(str1==null||str2==null){  
  19.             return -1;  
  20.         }  
  21.          
  22.         int m = str1.length();  
  23.         int n = str2.length();  
  24.         for(int i =1;i<=m;i++){  
  25.             c[i][0]=0;  
  26.         }  
  27.         for(int i=0;i<=n;i++){  
  28.             c[0][i]=0;  
  29.         }  
  30.         for(int i =1;i<=m;i++){  
  31.             for(int j =1;j<=n;j++){  
  32.                 if(str1.charAt(i-1) == str2.charAt(j-1)){  
  33.                     c[i][j] = c[i-1][j-1]+1;  
  34.                 }  
  35.                 else if(c[i-1][j]>=c[i][j-1]){  
  36.                     c[i][j] = c[i-1][j];  
  37.                 }  
  38.                 else  
  39.                     c[i][j] = c[i][j-1];  
  40.             }  
  41.         }  
  42.         return c[m][n];  
  43.     }  
  44.     public static void print_lcs(String str1,String str2,int[][] c){  
  45.          
  46.         int k=0;  
  47.         int i=str1.length();  
  48.         int j=str2.length();  
  49.         char[] temp = new char[c[i][j]];  
  50.         while(c[i][j]>0){  
  51.             if(str1.charAt(i-1) == str2.charAt(j-1)){  
  52.                 temp[k] = str1.charAt(i-1);  
  53.                 k++;  
  54.                 i--;  
  55.                 j--;  
  56.             }  
  57.             else if(c[i][j] == c[i-1][j])  
  58.                 i--;  
  59.             else  
  60.                 j--;  
  61.         }  
  62.         for(int l=temp.length-1;l>=0;l--){  
  63.             System.out.print(temp[l]);  
  64.         }  
  65.          
  66.     }  
  67.  
  68. }  
  69.  
  70.  
  71. //java/7037

回复 "动态规划之最长公共子序列Java实现"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666