请用C语言实现最长公共子序列问题，实验数据采用手动输入的方式。给出解决问题的思路及简要步骤，以及完整代码

在C语言中，我们可以使用动态规划的方法来解决最长公共子序列（Longest Common Subsequence，LCS）问题。这个问题通常涉及到两个字符串，我们寻找这两个字符串中最长的共同子序列，但不需要它们连续出现。

以下是解决问题的思路和步骤：

1. **思路**：
- 创建一个二维数组，其中数组的行代表第一个字符串的字符，列代表第二个字符串的字符。
- 初始化数组的第一行和第一列，因为每个字符串单独一个字符都是其自身的子序列，所以长度为1。
- 从第二行开始遍历，对于每个位置 `(i, j)`，比较当前字符是否相等。如果相等，则该位置的值等于上一行和上一列对应位置加1；如果不相等，则取上一行和当前列、以及当前行和上一列的最大值。
- 最终数组右下角的值就是两个字符串的最长公共子序列长度。

2. **简要步骤**：
- 输入两个字符串
- 初始化二维数组
- 遍历矩阵，记录最大公共子序列长度
- 根据记录的长度回溯找到子序列

下面是一个简单的C语言实现：

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

// 获取最长公共子序列长度
int lcs(char *str1, char *str2, int m, int n) {
    int dp[m+1][n+1];
    int i, j;

    // 填充dp表
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (str1[i-1] == str2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    return dp[m][n];
}

// 获取最长公共子序列
void printLCS(char *str1, char *str2, int m, int n, int dp[m+1][n+1]) {
    int index = dp[m][n];

    // 从右下角回溯
    char lcs[index + 1];
    lcs[index] = '\0'; // 满足空终止符条件

    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i-1] == str2[j-1]) {
            lcs[index-1] = str1[i-1]; // 将当前字符添加到结果中
            i--;
            j--;
            index--;
        } else if (dp[i-1][j] > dp[i][j-1]) { // 如果左上方更大
            i--;
        } else {
            j--;
        }
    }
    printf("最长公共子序列: %s\n", lcs);
}

int main() {
    char str1[100], str2[100];
    printf("请输入第一个字符串: ");
    fgets(str1, sizeof(str1), stdin);
    str1[strlen(str1) - 1] = '\0'; // 去掉换行符
    printf("请输入第二个字符串: ");
    fgets(str2, sizeof(str2), stdin);
    str2[strlen(str2) - 1] = '\0';

    int m = strlen(str1);
    int n = strlen(str2);

    printf("最长公共子序列的长度: %d\n", lcs(str1, str2, m, n));
    printLCS(str1, str2, m, n, NULL); // 使用lcs函数获取并打印子序列

    return 0;
}