动态规划-最长公共子串

# include
# include
# define MAX(a, b) ((a) > (b) ? (a) : (b))
int LCSubstring1(char * str1, char * str2);
int LCSubstring2(char * str1, char * str2);
int LCSubstring3(char * str1, char * str2);
int main(void){
    char * str1 = "bcda";
    char * str2 = "abcde";
    printf("%d\n", LCSubstring1(str1, str2));
    printf("%d\n", LCSubstring2(str1, str2));
    printf("%d\n", LCSubstring3(str1, str2));
    system("pause");
    return 0;
}
int LCSubstring1(char * str1, char * str2){
    if(NULL == str1 || NULL == str2)
        return 0;
    int n = strlen(str1);
    int m = strlen(str2);
    int ** dp = (int**)calloc((n+1), sizeof(int*));
    for(int i = 0; i <= n; i++){
        dp[i] = (int*)calloc((m+1), sizeof(int));
    }
    //dp[j][k]为分别以第j和第k个字符结尾的两个字符串的最长公共子串长度
    int max = 0;
    for(int j = 1; j <= n; j++){
        for(int k = 1; k <= m; k++){
            if(str1[j-1] == str2[k-1]){
                dp[j][k] = dp[j-1][k-1] + 1;
            }
            max = MAX(max, dp[j][k]);
        }
    }
    return max;
}
int LCSubstring2(char * str1, char * str2){
    if(NULL == str1 || NULL == str2)
        return 0;
    int n = strlen(str1);
    int m = strlen(str2);
    int * dp = (int*)calloc((m+1), sizeof(int));
    //dp[k]为分别以第某个和第k个字符结尾的两个字符串的最长公共子串长度
    int max = 0;
    for(int j = 1; j <= n; j++){
        int temp = 0;
        for(int k = 1; k <= m; k++){
            int Topleft = temp;
            temp = dp[k];
            if(str1[j-1] == str2[k-1]){
                dp[k] = Topleft + 1;
            }
            max = MAX(max, dp[k]);
        }
    }
    return max;
}
int LCSubstring3(char * str1, char * str2){
    if(NULL == str1 || NULL == str2)
        return 0;
    char * rows = str1;
    char * cols = str2;
    if(strlen(str1) < strlen(str2)){
         rows = str2;
         cols = str1;
    }
    int row = strlen(rows);
    int col = strlen(cols);
    int * dp = (int*)calloc((col+1), sizeof(int));
    int max = 0;
    for(int j = 1; j <= row; j++){
        int temp = 0;
        for(int k = 1; k <= col; k++){
            int topleft = temp;
            temp = dp[k];
            if(rows[j-1] == cols[k-1]){
                dp[k] = topleft + 1;
            }
            max = MAX(max, dp[k]);
        }
    }
    return max;
}