algorithm - 最長共通部分列 (LCS) の削減

Question

私は 2 つの文字列の LCS に関する問題に取り組んでおり、LCS の一般的なケースからバイナリ バージョンへの縮小があるかどうか疑問に思っていました。つまり、ビット文字列の LCS を解くことで、LCS を任意の (しかし有限) アルファベット基数。

そのような削減が存在することは (問題のさまざまなバージョンのアルゴリズムの複雑さに基づいて) 合理的に思えますが、そのようなものは見つかりませんでした。