最⻓公共⼦序列和最⻓公共⼦串

最长公共子序列

f[i][j] i表示A的位，j表示B的位

- i=0或者j=0，返回长度0

- i>0,j>0,且xi=yj；返回长度C(i-1,j-1)+1;

- i>0,j>0，且xi !=yj，返回长度max(c(i-1,j),c(i,j-1));

 1 int LongCommonSubquence(string A,string b)
 2 {
 3     if(A==NULL || A.length() ==0)
 4         return 0;
 5     if(B==NULL || B.length() ==0)
 6         return 0;
 7     
 8     int LenA=A.length();
 9     int LenB=B.length();
10     int[][] lcs=new int[1+lenA][1+lenB];
11     
12     for(int i=1;i<1+lenA;i++){
13         for(int j=1;j<1+LenB;j++){
14             if(A.charAt(i-1)==B.charBt(j-1)){
15                 lcs[i][j]=1+lcs[i-1][j-1];
16             }else{
17                 lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1]);
18             }
19         }
20     }
21     return lsc[LenA][LenB];
22 }

//最长公共字串（动态规划）

 1 int lcs(String str1, String str2) {
 2     int len1 = str1.length();
 3     int len2 = str2.length();
 4     int result = 0;     //记录最长公共子串长度
 5     int c[][] = new int[len1+1][len2+1];
 6     for (int i = 0; i <= len1; i++) {
 7         for( int j = 0; j <= len2; j++) {
 8             if(i == 0 || j == 0) {
 9                 c[i][j] = 0;
10             } else if (str1.charAt(i-1) == str2.charAt(j-1)) {
11                 c[i][j] = c[i-1][j-1] + 1;
12                 result = max(c[i][j], result);
13             } else {
14                 c[i][j] = 0;
15             }
16         }
17     }
18     return result;
19 }

转载请说明出处！

最⻓公共⼦序 列和最⻓公共⼦串

最⻓公共⼦序列和最⻓公共⼦串