最长公共子序列(二)

#define max(a,b) (a>b?a:b)
char* LCS(char* s1, char* s2 ) {
    int dp[10000][10000], i, j, maxLen=0, max_i=0, max_j=0;
    
    for(i=0; i<strlen(s1); i++) {
        dp[i][0] = 0;
        if(s1[i]==s2[0]) {
            maxLen = 1;
            break;
        }
    }
    for(; i<strlen(s1); i++) {
        dp[i][0] = 1;
        max_i = i;
        max_j = 0;
    }
    
    for(j=0; j<strlen(s2); j++) {
        dp[0][j] = 0;
        if(s2[j]==s1[0]) {
            maxLen = 1;
            break;
        }
    }
    for(; j<strlen(s2); j++) {
        dp[0][j] = 1;
        max_i = 0;
        max_j = j;
    }

    for(i=1; i<strlen(s1); i++) {
        for(j=1; j<strlen(s2); j++) {
            if(s1[i]==s2[j]) {
                dp[i][j] = dp[i-1][j-1]+1;
                if(maxLen<dp[i][j]) {
                    maxLen = dp[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
            else {
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
                if(maxLen<dp[i][j]) {
                    maxLen = dp[i][j];
                    max_i = i;
                    max_j = j;
                }
            }
            
        }
    }

    char* res=(char*)malloc(maxLen+1);
    res[maxLen--]='\0';
    while(max_i>0 && max_j>0) {
        if(dp[max_i][max_j]>dp[max_i][max_j-1] && dp[max_i][max_j]>dp[max_i-1][max_j]) {
            res[maxLen--]=s1[max_i];
            max_i--, max_j--;
        }
        else if(dp[max_i][max_j]==dp[max_i][max_j-1] && dp[max_i][max_j]>dp[max_i-1][max_j]) 
            max_j--;
        else if(dp[max_i][max_j]>dp[max_i][max_j-1] && dp[max_i][max_j]==dp[max_i-1][max_j]) 
            max_i--;
        else 
            max_i--, max_j--;
    }
    
    while(max_i--)
    {
        if(dp[max_i][0]>dp[max_i-1][0]) 
            break;
    }
 
    if(max_i<0)
        max_i++;
     res[maxLen]=s1[max_i];
    
    if(strlen(res)==0)
        return "-1";

    return res;
}