#include <stdio.h> #include <string.h> #define MAXLEN 100 int dp[MAXLEN][MAXLEN]; // DP 数组，存储当前最长公共子序列长度 int prev[MAXLEN][MAXLEN]; // 用于记录 DP 数组中选择的方向，用于回溯得到最长公共子序列 void print_lcs(char X[], int i, int j) { if (i == 0 || j == 0) return; // 递归边界 if (prev[i][j] == 1) { print_lcs(X, i-1, j-1); printf("%c", X[i-1]); // 输出当前字符 } else if (prev[i][j] == 2) { print_lcs(X, i-1, j); } else { print_lcs(X, i, j-1); } } void lcs(char X[], char Y[]) { int m = strlen(X); int n = strlen(Y); // 计算 DP 数组 for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; continue; } if (X[i-1] == Y[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; prev[i][j] = 1; // 向左上方 } else { if (dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; prev[i][j] = 2; // 向上方 } else { dp[i][j] = dp[i][j-1]; prev[i][j] = 3; // 向左方 } } } } // 输出最长公共子序列 printf("LCS is: "); print_lcs(X, m, n); printf("\n"); } int main() { char X[MAXLEN], Y[MAXLEN]; printf("请输入两个字符串X和Y：\n"); scanf("%s%s", X, Y); lcs(X, Y); return 0; }测试算法的正确性和性能

为了测试算法的正确性和性能，可以准备一些测试用例，包括特殊情况和一般情况，并且记录算法运行时间。以下是一个简单的测试代码：

#include <stdio.h>
#include <string.h>
#include <time.h>

#define MAXLEN 100

int dp[MAXLEN][MAXLEN];
int prev[MAXLEN][MAXLEN];

void print_lcs(char X[], int i, int j) {
    if (i == 0 || j == 0) return;

    if (prev[i][j] == 1) {
        print_lcs(X, i-1, j-1);
        printf("%c", X[i-1]);
    } else if (prev[i][j] == 2) {
        print_lcs(X, i-1, j);
    } else {
        print_lcs(X, i, j-1);
    }
}

void lcs(char X[], char Y[]) {
    int m = strlen(X);
    int n = strlen(Y);

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0) {
                dp[i][j] = 0;
                continue;
            }

            if (X[i-1] == Y[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                prev[i][j] = 1;
            } else {
                if (dp[i-1][j] >= dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j];
                    prev[i][j] = 2;
                } else {
                    dp[i][j] = dp[i][j-1];
                    prev[i][j] = 3;
                }
            }
        }
    }

    printf("LCS is: ");
    print_lcs(X, m, n);
    printf("\n");
}

int main() {
    char X[MAXLEN], Y[MAXLEN];

    printf("请输入两个字符串X和Y：\n");
    scanf("%s%s", X, Y);

    clock_t start = clock();
    lcs(X, Y);
    clock_t end = clock();

    printf("算法运行时间：%f秒\n", (double)(end - start) / CLOCKS_PER_SEC);

    return 0;
}

这个测试代码首先读入两个字符串，然后计算最长公共子序列并输出，最后记录算法的运行时间。可以用不同的输入进行多次测试，观察算法的正确性和性能表现。