4

2つの文字列の間に存在する可能な最長のサブシーケンスの量を計算しようとしています。

例：String X = "efgefg"; 文字列Y="efegf";

出力：最長の一般的なシーケンスの数は次のとおりです：3（つまり、efeg、efef、efgf-これはアルゴリズムによって計算する必要はありません。デモのためにここに示しています）

ここでの一般的な考え方に基づく動的計画法を使用して、O（| X | * | Y |）でこれを行うことができました：最も安いパスアルゴリズム。

より良いランタイムでこの計算を効率的に行う方法を誰かが考えることができますか？

-ジェイソンのコメントに応えて編集。

4

4 に答える 4

1

最長共通部分列問題は、よく研究されている CS 問題です。

ここでそれを読みたいと思うかもしれません: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

于 2010-03-01T14:45:49.683 に答える
0

わかりませんが、声に出して考えようとする試みがいくつかあります。

私が構築できた最悪のケースは、指数 - 2**(0.5 |X|) - 最長共通サブシーケンスの数です。

X = "aAbBcCdD..."
Y = "AaBbCcDd..."

最長の一般的なサブシーケンスには、{A、a} のうちの 1 つ、{B、b} のうちの 1 つなどが含まれます。 128はすでに巨大です。）

ただし、それらをカウントするために必ずしもすべてのサブシーケンスを生成する必要はありません。あなたが O(|X| * |Y|) を持っているなら、あなたはすでにそれよりも優れています! このことから学べることは、あなたのアルゴリズムよりも優れたアルゴリズムは、実際のサブシーケンスを生成しようとしてはならないということです。

于 2010-02-14T18:59:23.610 に答える