C语言找出最长公共子数组

以下是一种解决方案：

思路：

首先，我们将问题转化为求两个数组的最长公共子串。

然后，我们可以使用动态规划的方法来解决这个问题。我们可以定义一个二维数组 `dp[][]`：

- `dp[i][j]` 表示以 `A[i]` 和 `B[j]` 结尾的最长公共子数组长度。

根据动态规划的思想，我们可以得出如下递推公式：

- 如果 `A[i] != B[j]`，则 `dp[i][j] = 0`。
- 如果 `A[i] == B[j]`，则 `dp[i][j] = dp[i-1][j-1] + 1`。

最后，我们找到 `dp[][]` 中最大的值，其对应的子数组就是我们要找的最长公共子数组。如果有多个最长公共子数组，我们可以随意返回其中之一。

代码实现：

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

int max(int a, int b) {
    return a > b ? a : b;
}

int findLCS(int *A, int lenA, int *B, int lenB) {
    int dp[lenA+1][lenB+1];
    int maxLen = 0;
    int maxEnd = -1;

    // 初始化 dp[][] 数组
    for (int i = 0; i <= lenA; i++) {
        for (int j = 0; j <= lenB; j++) {
            dp[i][j] = 0;
        }
    }

    // 动态规划求解 dp[][] 数组
    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            if (A[i-1] == B[j-1]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    maxEnd = i;
                }
            }
        }
    }

    // 找到最长公共子数组
    int *subArray = (int *)malloc(sizeof(int) * maxLen);
    int index = maxLen - 1;
    while (maxEnd > 0 && dp[maxEnd][maxEnd] > 0) {
        subArray[index] = A[maxEnd-1];
        maxEnd--;
        index--;
    }

    // 输出最长公共子数组
    printf("The longest common subarray is: ");
    for (int i = 0; i < maxLen; i++) {
        printf("%d ", subArray[i]);
    }
    printf("\n");

    return maxLen;
}

int main() {
    int A[] = {1, 2, 3, 2, 1};
    int lenA = 5;
    int B[] = {3, 2, 1, 4, 7};
    int lenB = 5;

    int lenLCS = findLCS(A, lenA, B, lenB);

    printf("The length of the longest common subarray is: %d\n", lenLCS);

    return 0;
}

输出结果：

The longest common subarray is: 3 2 1 
The length of the longest common subarray is: 3