编辑代码

#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 word you entered.\n");
        return -1;
    }

    int **dpArray = (int **)malloc(lengthA * sizeof(int *));
    for (int i = 0; i < lengthA; ++i) {
        dpArray[i] = (int *)malloc(lengthB * sizeof(int));
    }

    int maxLength = 0;

    for (int i = 0; i < lengthA; ++i) {
        for (int j = 0; j < lengthB; ++j) {
            if (toupper(wordA[i]) == toupper(wordB[j])) {
                dpArray[i][j] = 1;
                if (i > 0 && j > 0) {
                    dpArray[i][j] += dpArray[i - 1][j - 1];
                }
                if (maxLength < dpArray[i][j]) {
                    sequence[maxLength] = toupper(wordA[i]);
                    maxLength = dpArray[i][j];
                }
            } else {
                dpArray[i][j] = 0;
                if (i > 0) {
                    dpArray[i][j] = dpArray[i - 1][j];
                }
                if (j > 0 && dpArray[i][j] < dpArray[i][j - 1]) {
                    dpArray[i][j] = dpArray[i][j - 1];
                }
            }
        }
    }

    maxLength = dpArray[lengthA - 1][lengthB - 1];

    for (int i = 0; i < lengthA; i++) {
        free(dpArray[i]);
    }

    free(dpArray);

    return maxLength;
}

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

    char longestCommonSequence[100];

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

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

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

    length = getLongestCommonSequence(wordA, wordB, longestCommonSequence);

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

    return 0;
}