科研速览 · Science Skim继续刷下去 · Keep skimming →
◇ arXiv2026-08-14· cs.DS

MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings

Wing-Kai Hon, Dominik Köppl, Jun-Hong Wang

原始摘要(英文原文)· Original abstract
We study a tie-breaking variant of the longest common subsequence problem on run-length encoded strings. Given two strings, the goal is first to maximize the number of equal aligned character pairs, as in the classical longest common subsequence problem, and then, among all such alignments, to minimize the alignment length. Equivalently, after maximizing the number of equal pairs, we minimize the number of insertions and deletions. We show that this problem admits a simple block-boundary dynamic program. If the input strings have lengths $N$ and $M$, and their run-length encodings have $n$ and $m$ runs, respectively, the algorithm runs in $O(mN+nM)$ time using $O(nm)$ space. The algorithm treats every pair of runs as a homogeneous block with an explicit transfer function and stores dynamic-programming values only on run boundaries.
读原文 · Read the paper ↗

AI 追问PRO

登录后使用 AI 追问

讨论区

登录后参与讨论

相关论文 · Related

MacCorles: Minimum Alignment Cost Computation on Run-Length Encoded Strings — 科研速览 Science Skim