30807：最长公共子序列重建

题目

求两个任意字节序列的最长公共子序列，并按固定规则重建一条结果。

解析

dp[i][j] 表示左序列前 i 个字节和右序列前 j 个字节的最长公共子序列长度。末字节相等时从左上角加一；不等时取向上和向左的较大值。回溯时相等优先向上，因而相同输入总会得到相同输出。

回溯结果从后向前填入输出数组，最后再提交 out_length；容量不足和分配失败都发生在写出之前。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>

bool lcs_u8(
    const unsigned char *left,
    size_t left_count,
    const unsigned char *right,
    size_t right_count,
    unsigned char *out_sequence,
    size_t capacity,
    size_t *out_length
) {
    if (out_length == NULL ||
        (left_count > 0 && left == NULL) ||
        (right_count > 0 && right == NULL)) {
        return false;
    }
    if (left_count == 0 || right_count == 0) {
        *out_length = 0;
        return true;
    }
    if (left_count == SIZE_MAX || right_count == SIZE_MAX) {
        return false;
    }
    size_t columns = right_count + 1;
    if (left_count + 1 > SIZE_MAX / columns ||
        (left_count + 1) * columns >
            SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    size_t *dp = calloc(
        (left_count + 1) * columns,
        sizeof *dp
    );
    if (dp == NULL) {
        return false;
    }
    for (size_t i = 1; i <= left_count; ++i) {
        for (size_t j = 1; j <= right_count; ++j) {
            size_t index = i * columns + j;
            if (left[i - 1] == right[j - 1]) {
                size_t previous = dp[(i - 1) * columns + j - 1];
                if (previous == SIZE_MAX) {
                    free(dp);
                    return false;
                }
                dp[index] = previous + 1;
            } else {
                size_t up = dp[(i - 1) * columns + j];
                size_t side = dp[i * columns + j - 1];
                dp[index] = up >= side ? up : side;
            }
        }
    }

    size_t length = dp[left_count * columns + right_count];
    if (length > capacity || (length > 0 && out_sequence == NULL)) {
        free(dp);
        return false;
    }
    size_t i = left_count;
    size_t j = right_count;
    size_t cursor = length;
    while (i > 0 && j > 0) {
        if (left[i - 1] == right[j - 1]) {
            out_sequence[--cursor] = left[i - 1];
            --i;
            --j;
        } else {
            size_t up = dp[(i - 1) * columns + j];
            size_t side = dp[i * columns + j - 1];
            if (up >= side) {
                --i;
            } else {
                --j;
            }
        }
    }
    free(dp);
    *out_length = length;
    return true;
}

动态规划表的时间和额外空间复杂度都是 $O(nm)$；回溯过程为 $O(n+m)$。