编辑代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int getLongestCommonSequence(char* wordA, char* wordB, char** sequence) {
    int lengthA = strlen(wordA);
    int lengthB = strlen(wordB);

    if (0 == lengthA || 0 == lengthB) {
        printf("Please check the words you entered.\n");
        return -1;
    }

    // 创建表格，横轴是字符串A，纵轴是字符串B
    int** dpArray = (int**)malloc((lengthA + 1) * sizeof(int*));
    for (int i = 0; i <= lengthA; ++i) {
        dpArray[i] = (int*)malloc((lengthB + 1) * sizeof(int));
    }

    int maxLength = 0;

    // 填充表格
    for (int i = 0; i <= lengthA; ++i) {
        for (int j = 0; j <= lengthB; ++j) {
            if (i == 0 || j == 0) {
                dpArray[i][j] = 0;
            }
            else if (toupper(wordA[i - 1]) == toupper(wordB[j - 1])) {
                dpArray[i][j] = dpArray[i - 1][j - 1] + 1;
                if (maxLength < dpArray[i][j]) {
                    maxLength = dpArray[i][j];
                }
            }
            else {
                dpArray[i][j] = (dpArray[i - 1][j] > dpArray[i][j - 1]) ? dpArray[i - 1][j] : dpArray[i][j - 1];
            }
        }
    }

    // 构造最长公共子序列
    *sequence = (char*)malloc((maxLength + 1) * sizeof(char));
    (*sequence)[maxLength] = '\0';
    int i = lengthA, j = lengthB, k = maxLength - 1;
    while (i > 0 && j > 0) {
        if (toupper(wordA[i - 1]) == toupper(wordB[j - 1])) {
            (*sequence)[k] = toupper(wordA[i - 1]);
            i--;
            j--;
            k--;
        }
        else if (dpArray[i - 1][j] > dpArray[i][j - 1]) {
            i--;
        }
        else {
            j--;
        }
    }

    // 释放动态规划表格的内存
    for (int i = 0; i <= lengthA; ++i) {
        free(dpArray[i]);
    }
    free(dpArray);

    return maxLength;
}

int main() {
    char wordA[] = "MIGRATION";
    char wordB[] = "Migrapion";

    char* longestCommonSequence = NULL;

    int length = getLongestCommonSequence(wordA, wordB, &longestCommonSequence);

    printf("The length of the longest common sequence is %d\n", length);
    printf("%s\n", longestCommonSequence);

    free(longestCommonSequence);

    strcpy(wordA, "Fish");
    strcpy(wordB, "Hist");

    longestCommonSequence = NULL;

    length = getLongestCommonSequence(wordA, wordB, &longestCommonSequence);

    printf("The length of the longest common sequence is %d\n", length);
    printf("%s\n", longestCommonSequence);

    free(longestCommonSequence);

    return 0;
}