30803：编辑距离

题目

求两个字节序列之间允许插入、删除和替换时的最小编辑次数，并把动态规划存储压缩为一行。

解析

令当前行的第 j 项表示一个序列的当前前缀与另一个序列前 j 个字节的编辑距离。更新一个位置时需要三个旧值：

• 左侧：插入一个字节；
• 上方：删除一个字节；
• 左上方：当前字节相同则不增加代价，否则替换一次。

让较短序列对应列，可以把额外空间降到 $O(min(n,m))$。更新前暂存左上方和上方旧值，便可以安全覆盖当前行。

解析

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

static size_t add_one_saturated(size_t value) {
    return value == SIZE_MAX ? SIZE_MAX : value + 1;
}

static size_t minimum_three(
    size_t first,
    size_t second,
    size_t third
) {
    size_t result = first < second ? first : second;
    return result < third ? result : third;
}

bool edit_distance(
    const unsigned char *left,
    size_t left_count,
    const unsigned char *right,
    size_t right_count,
    size_t *out_distance
) {
    if (out_distance == NULL ||
        (left_count > 0 && left == NULL) ||
        (right_count > 0 && right == NULL)) {
        return false;
    }

    if (left_count == 0) {
        *out_distance = right_count;
        return true;
    }
    if (right_count == 0) {
        *out_distance = left_count;
        return true;
    }

    const unsigned char *row_sequence = left;
    size_t row_count = left_count;
    const unsigned char *column_sequence = right;
    size_t column_count = right_count;

    if (left_count < right_count) {
        row_sequence = right;
        row_count = right_count;
        column_sequence = left;
        column_count = left_count;
    }

    if (column_count == SIZE_MAX ||
        column_count + 1 >
            SIZE_MAX / sizeof(size_t)) {
        return false;
    }

    size_t *row = malloc(
        (column_count + 1) * sizeof *row
    );
    if (row == NULL) {
        return false;
    }

    for (size_t j = 0; j <= column_count; ++j) {
        row[j] = j;
    }

    for (size_t i = 0; i < row_count; ++i) {
        size_t upper_left = row[0];
        row[0] = i + 1;

        for (size_t j = 0; j < column_count; ++j) {
            size_t above = row[j + 1];
            size_t insertion = add_one_saturated(row[j]);
            size_t deletion = add_one_saturated(above);
            size_t replacement = upper_left;

            if (row_sequence[i] != column_sequence[j]) {
                replacement = add_one_saturated(replacement);
            }

            row[j + 1] = minimum_three(
                insertion,
                deletion,
                replacement
            );
            upper_left = above;
        }
    }

    size_t result = row[column_count];
    free(row);
    *out_distance = result;
    return true;
}

来源与改编

题型改编自 CSES Problem Set 的 Edit Distance，采用 CC BY-NC-SA 4.0；本题改为任意字节序列接口，并要求一行存储与分配失败语义。