suffix-tree - 同じ位置からすべての可能な最長共通部分列を見つける方法

Question

複数の固定長文字列の同じ位置から、可能な限り最長の共通部分列をすべて見つけようとしています (合計で 700 個の文字列があり、各文字列には 25 個のアルファベットがあります)。最長の共通サブシーケンスには、少なくとも 3 つのアルファベットが含まれ、少なくとも 3 つの文字列に属している必要があります。だから私が持っている場合：

String test1 = "abcdeug";
String test2 = "abxdopq";
String test3 = "abydnpq";
String test4 = "hzsdwpq";

私は答えが必要です：

String[] Answer = ["abd", "dpq"];

私の1つの問題は、これをできるだけ速くする必要があることです。サフィックスツリーで答えを見つけようとしていますが、サフィックスツリーメソッドの解決策は.サフィックスツリーは["ab","pq"]複数の文字列から連続した部分文字列しか見つけることができません.共通の最長共通部分列アルゴリズムはこの問題を解決できません. 時間コストを抑えてこれを解決する方法を知っている人はいますか? ありがとう

Answer 1

ハッシュを使用してみてください。
各文字列は最大 25 文字です。これは、2^25 のサブシーケンスがあることを意味します。各文字列を取得し、すべての 2^25 ハッシュを計算します。次に、すべての文字列のすべてのハッシュを結合し、どれが少なくとも 3 回含まれているかを計算します。これらのサブシーケンスの長さを取得するには、ハッシュだけでなく、そのハッシュのサブシーケンスを決定するペアを格納する必要があります<hash, subsequence_pointer>(subsequence_pointer最も簡単な方法は、すべての文字列のすべてのハッシュを列挙し、ハッシュ番号を格納することです)。
アルゴリズムに基づいて、最悪の場合 (700 文字列、それぞれ 25 文字) のプログラムは数分間実行されます。