Участник:Easik/shortest-common-supersequence

Материал из DISCOPAL
Перейти к: навигация, поиск

C \ gcc

char *shortestCommonSupersequence(char *str1, char *str2) {
 
    int i, j;
    int tmp;
    char ch;
 
    int size1 = (int)strlen(str1);
    int size2 = (int)strlen(str2);
 
    int stack_size = size1 + size2 + 1; /* Enough space for all situations */
    char *stack = (char *)calloc(stack_size, sizeof(char));
    stack[stack_size - 1] = '\0';
    int stack_idx = stack_size - 2;
 
    int dp[size1 + 1][size2 + 1];
    for (i = 0; i <= size1; i++) { for (j = 0; j <= size2; j++) { dp[i][j] = 0; } }
 
    for (i = 1; i <= size1; i++) {
 
        for (j = 1; j <= size2; j++) {
 
            tmp = (dp[i - 1][j] >= dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1];
            dp[i][j] = (str1[i - 1] == str2[j - 1]) ? (1 + dp[i - 1][j - 1]) : tmp;
 
        }
 
    }
 
    while (size1 || size2) {
 
        if (size1 == 0) {
 
            size2--;
            ch = str2[size2];
 
        } else if (size2 == 0) {
 
            size1--;
            ch = str1[size1];
 
        } else if (str1[size1 - 1] == str2[size2 - 1]) {
 
            size1--;
            size2--;
            ch = str1[size1];
 
        } else if (dp[size1 - 1][size2] == dp[size1][size2]) {
 
            size1--;
            ch = str1[size1];
 
        } else if (dp[size1][size2 - 1] == dp[size1][size2]) {
 
            size2--;
            ch = str2[size2];
 
        }
 
        stack[stack_idx--] = ch;
 
    }
 
    stack_idx++;
 
    i = 0;
    if (stack_idx > 0) {
 
        while (i + stack_idx < stack_size) {
 
            stack[i] = stack[i + stack_idx];
            if (stack[i + stack_idx] == '\0') break;
            i++;
 
        }
 
    }
 
    return stack;
 
}