N個のシーケンスの中で最も長い共通サブシーケンス（diff目的のため）

Question

N個の文字列の中で最も長い共通部分シーケンスを探したい。私は、2つの文字列の動的プログラミングを使用するアルゴリズムを持っていますが、私はそれをNに拡張すると、N次元の配列が必要なので、指数関数的な量のメモリを消費します。それはオプションではありません。

一般的なケース（90％）では、ほとんどすべての文字列が同じになります。

N個のシーケンスをそれぞれ2つのストリングのN/2ペアで分割しようとすると、各ペアごとに2つのストリングのLCSを別々に実行すると、N/2のサブシーケンスが生成されます。私は重複を削除して、入力のすべての文字列に共通のサブシーケンスが1つしかない限り、このプロセスを繰り返します。

紛失しているものがありますか？それはNハードの問題の解決策のようには見えません...

私は文字列の各ペアでLCSを呼び出すたびに複数のサブシーケンスを解決策として使うことができますが、次の呼び出しで入力として使用するこれらのサブシーケンスのうち、おそらく私の最終的なサブシーケンスは可能な限り最長ではありませんが、私のニーズに合ったものがあります。

私は1つのペアのすべての可能な解を使用して、別のペアの可能なすべての解を組み合わせようとすると（それぞれに複数の解がある可能性があります）、指数関数的な時間に終わることがあります。私は正しい？

Answer 1

はい、正確さが欠落しています。文字列ペアのLCSが、セット全体のLCSと重複することは保証されません。この例を考えてみましょう：

aaabb1xyz 
aaabb2xyz 
cccdd1xyz 
cccdd2xyz 

あなたが与えられたために、これらをペアリングする場合は、セットのためxyzを逃し、aaabbとcccddののLCSを得るでしょう。

あなたが言うように、文字列はほとんどすべて同じですが、違いはあなたにとって問題ではないかもしれません。同じでない文字列が "中央値"文字列に非常に似ている場合、インクリメンタルソリューションはあなたの目的に十分適しています。

もう1つの可能性は、メディアン文字列が出現するまでランダムな文字列ペアでLCSを実行することです。その共通点から始めれば、「十分に良い」ソリューションが得られるはずです。