两个字符串的最长公共子序列的长度

两个字符串的最长公共子序列（max common sequence）

九度OJ链接：http://ac.jobdu.com/problem.php?pid=1042

两个字符串的最长公共子序列是指给定两个字符串，找出这两个字符串中相同的字符的序列，这些字符不要求连续（注意与最长公共子串的区别，最长公共子串要求字符是连续的）

举个例子，比如字符串 X: "FABCDF" , Y: "ABFDE"

X和Y的最长公共子序列长度为 3，即 "ABD"，注意"AB"和"D"并没有连续。

X和Y的最长公共子串的长度为2，即"AB"

假设 L(Xi,Yj) 表示X字符串从0-i的子串与Y字符串从0-j的子串的最长公共子序列长度，CX[i]表示字符串X在索引为i处的字符，CY[j]表示字符串Y在索引为j处的字符，则有（状态转移方程）：

L(Xi,Yj)=L(X(i-1),Y(j-1))+1,  如果CX[i]==CY[j];

L(Xi,Yj)=max( L(X(i-1),Yj) , L(Xi,Y(j-1)) ),  如果CX[i]!=CY[j]

就上面的例子来看，由于CX[5]='F', CY[4]='E'，即CX[5]!=CY[4]，因此L(X5,Y4)=max( L(X4,Y4) , L(X5,Y3) )，即字符串"FABCDF"与"ABFD"的最大公共子序列与字符串"FABCD"与"ABFDE"的最大公共子序列二者的较大者

递归代码：

 

 
  1. public int maxCommomSubSequence(String s1,String s2){  
  2.     if(s1.length()<=0 || s2.length()<=0)  
  3.         return 0;  
  4.     if(s1.length()==1 &&s2.length()==1){  
  5.         return s1.charAt(0)==s2.charAt(0)?1:0;  
  6.     }  
  7.     if(s1.charAt(s1.length()-1)==s2.charAt(s2.length()-1)){  
  8.         return 1+maxCommomSubSequence(s1.substring(0, s1.length()-1),s2.substring(0,s2.length()-1));  
  9.     }else  
  10.         return Math.max(maxCommomSubSequence(s1.substring(0, s1.length()-1),s2.substring(0,s2.length())),  
  11.                 maxCommomSubSequence(s1.substring(0, s1.length()),s2.substring(0,s2.length()-1)));            
  12. }  

非递归代码：

 
  1. public int maxCommomSubSequence2(String s1,String s2){  
  2.     //用于保存Xi Yj 两个字符串的最大公共子序列长度  
  3.     int[][] commonSubSqsLen=new int[s1.length()][s2.length()];  
  4.     int maxLen=0;//表示两个字符串的最大公共子序列长度  
  5.     for(int i=0;i<s1.length();i++){  
  6.         for(int j=0;j<s2.length();j++){  
  7.             if(s1.charAt(i)==s2.charAt(j)){  
  8.                 if(i-1>=0&&j-1>=0){  
  9.                     commonSubSqsLen[i][j]=1+commonSubSqsLen[i-1][j-1];  
  10.                 }else{  
  11.                     commonSubSqsLen[i][j]=1;  
  12.                 }  
  13.             }else{  
  14.                 if(i-1>=0){  
  15.                     if(j-1>=0){  
  16.                         commonSubSqsLen[i][j]=Math.max(commonSubSqsLen[i][j-1],commonSubSqsLen[i-1][j]);  
  17.                     }else{  
  18.                         commonSubSqsLen[i][j]=commonSubSqsLen[i-1][j];  
  19.                     }  
  20.                 }else{  
  21.                     if(j-1>=0){  
  22.                         commonSubSqsLen[i][j]=commonSubSqsLen[i][j-1];  
  23.                     }else{  
  24.                         commonSubSqsLen[i][j]=0;  
  25.                     }  
  26.                 }                 
  27.             }  
  28.             if(commonSubSqsLen[i][j]>maxLen)  
  29.                 maxLen=commonSubSqsLen[i][j];  
  30.         }  
  31.     }  
  32.     for(int i=0;i<commonSubSqsLen.length;i++) //将矩阵打印出来  
  33.         System.out.println(Arrays.toString(commonSubSqsLen[i]));  
  34.     return maxLen;  
  35. }  

以上面这个例子，输出结果为：

  1. [0, 0, 1, 1, 1]  
  2. [1, 1, 1, 1, 1]  
  3. [1, 2, 2, 2, 2]  
  4. [1, 2, 2, 2, 2]  
  5. [1, 2, 2, 3, 3]  
  6. [1, 2, 3, 3, 3]  
  7. 3  
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/wwjldm/p/7095778.html