寻找两个数组的最长公共数字序列的问题

Question

这是我在 C 中的动态编程代码，但我不明白为什么我得到的输出是 1 而不是 3。

还有人可以建议我在找到最长的序列长度后应该如何继续打印最长的序列吗？

#include <stdio.h>

int max(int nmu1, int num2);
int findMaxLength(int a[], int b[], int n, int m);

int main() {
    int a[] = { 1, 2, 8, 2, 1 };
    int b[] = { 8, 2, 1, 4, 7 };

    int n = sizeof(a) / sizeof(a[0]);
    int m = sizeof(b) / sizeof(b[0]);

    printf("%d", findMaxLength(a, b, n, m));
}

int findMaxLength(int a[], int b[], int n, int m) {
    int dp[n + 1][m + 1];

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j >= 0; j--) {
            if (a[i] == b[j])
                dp[i][j] = dp[i + 1][j + 1] + 1;
        }
    }

    int maxm = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            maxm = max(maxm, dp[i][j]);
        }
    }

    return maxm;
}

int max(int num1, int num2) {
    return (num1 > num2) ? num1 : num2;
}

Answer 1

内部循环for (int j = 0; j >= 0; j--)什么都不做。你应该改为写：

for (int j = m - 1; j >= 0; j--)

要显示实际的子字符串，函数 findMaxLength 必须在找到新子串时跟踪最佳匹配的偏移量。您不能为此使用 maxm = max(maxm, dp[i][j]);，您必须使用显式测试。

这是修改后的版本：

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

int findMaxLength(const int a[], const int b[], int n, int m) {
    int dp[n + 1][m + 1];

    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++)
            dp[i][j] = 0;
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (a[i] == b[j])
                dp[i][j] = dp[i + 1][j + 1] + 1;
        }
    }

    int maxi = 0, maxj = 0, maxm = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (maxm < dp[i][j]) {
                maxm = dp[i][j];
                maxi = i;
                maxj = j;
            }
        }
    }

    if (maxm > 0) {
        printf("a[%d..%d] == b[%d..%d] == [ %d",
               maxi, maxi + maxm - 1, maxj, maxj + maxm - 1, a[maxi]);
        for (int i = 1; i < maxm; i++) {
            printf(", %d", a[maxi + i]);
        }
        printf(" ]\n");
    }
    return maxm;
}

int main() {
    int a[] = { 1, 2, 8, 2, 1 };
    int b[] = { 8, 2, 1, 4, 7 };
    int na = sizeof(a) / sizeof(a[0]);
    int nb = sizeof(b) / sizeof(b[0]);
    int len = findMaxLength(a, b, na, nb);
    printf("%d\n", len);
    return 0;
}

输出：

a[2..4] == b[0..2] == [ 8, 2, 1 ]
3

注意 findMaxLength 一次最多使用 2 个数组，因此如果将 3 个循环合并为一个，则可以将大小要求从 O(n.m ) 至 O(m):

int findMaxLength(const int a[], const int b[], int n, int m) {
    int dp[2][m + 1];
    int maxi = 0, maxj = 0, maxm = 0;

    for (int j = 0; j <= m; j++) {
        dp[0][j] = 0;
    }
    dp[1][m] = 0;

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            dp[1][j] = (a[i] == b[j]) * (dp[0][j + 1] + 1);
            if (maxm <= dp[1][j]) {
                maxm = dp[1][j];
                maxi = i;
                maxj = j;
            }
        }
        if (i-- == 0)
            break;
        for (int j = m - 1; j >= 0; j--) {
            dp[0][j] = (a[i] == b[j]) * (dp[1][j + 1] + 1);
            if (maxm <= dp[0][j]) {
                maxm = dp[0][j];
                maxi = i;
                maxj = j;
            }
        }
    }
    if (maxm > 0) {
        printf("a[%d..%d] == b[%d..%d] == [", maxi, maxi + maxm - 1, maxj, maxj + maxm - 1);
        for (int i = 0; i < maxm; i++) {
            printf(" %d", a[maxi + i]);
        }
        printf(" ]\n");
    }
    return maxm;
}

(a[i] == b[j]) * (dp[0][j + 1] + 1) 使用无分支代码计算 dp[1][j] 的值，这比您的 if 语句更有效。

使用此替代方案，我获得了 10x 更大数组大小（例如 16K 数字）的性能改进，但仍然遭受 O(n.m ) 时间复杂度。需要更高级的算法来降低这个经典的复杂性Longest common substring problem。

寻找两个数组的最长公共数字序列的问题

Problems with finding the Longest Common Sequence of numbers of two arrays

c

lcs