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

// 打印LCS的函数
void PrintLCS(int path[][100], char *x, int i, int j) {
    if (i == 0 || j == 0) {
        return;
    } 
    if (path[i][j] == 0) {
        PrintLCS(path, x, i - 1, j - 1);
        printf("%c", x[i - 1]);
    } else if (path[i][j] == 1) {
        PrintLCS(path, x, i - 1, j);
    } else {
        PrintLCS(path, x, i, j - 1);
    }
}

// 找到LCS的长度
int findLCS(int dp[][100], char *A, int n, char *B, int m) {
    // 初始化dp数组
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = 0; // 数组初始化
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) { // 执行状态转移方程
            if (A[i - 1] == B[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
            }
        }
    }
    return dp[n][m];
}

int main() {
    char x[] = "w8xta2px0i1jf4jfn8du8dk1fk2kvchd32";
    char y[] = "i3xsmdxwuv6a2yt520";

    int m = strlen(x);
    int n = strlen(y);
    
    // 创建二维数组
    int c[101][101];  // 101用于存储m+1和n+1的值
    int path[101][101];  // 路径数组

    // 初始化二维数组
    for (int i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int i = 0; i <= n; i++) {
        c[0][i] = 0;
    }

    // 实现LCS逻辑
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (x[i - 1] == y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
                path[i][j] = 1;  // 来自上方
            } else {
                c[i][j] = c[i][j - 1];
                path[i][j] = -1; // 来自左侧
            }
        }
    }

    // 输出c数组
    printf("c:\n");
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            printf("%d\t", c[i][j]);
        }
        printf("\n");
    }

    // 输出path数组
    printf("path:\n");
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            printf("%d\t", path[i][j]);
        }
        printf("\n");
    }

    printf("%s与%s的最长公共子序列为：\n", x, y);
    PrintLCS(path, x, m, n);

    return 0;
}