一連の文字列を区別する最も短い一意のサブシーケンス

Question

私はビットのN個の文字列（それぞれサイズM）X1 [0..M]、...、XN [0..M]を持っています。私は擬似コード/アルゴリズムが必要な最小の長さのサブシーケンス（必ずしも隣接している）を見つけるためには、それぞれの文字列で一意です。たとえば、

文字列が011011,011000,010010の場合、[2,4]（11,10,01）の部分列は各文字列で異なります。または部分列[2,4,5]（111,100,010）。または部分列[4,5]（11,00,10）。
ただし、部分列[0,1,5]（011,010,010）--->各文字列で一意ではありません。

編集：1 <= M <= 1000, 2 <= N <= 10。
編集：現在のところ、私の解決策は次のとおりです。 サブシーケンスの最小長はceil(log2(N))とN-1の間です。 ので、擬似コードは次のようになります。

for i = ceil(log2(N)) to N-1 : 
    check all subsequence of size i 
    if any subsequence distinguish all N strings, return i 

最初のステップは、すべての組み合わせmCiのを生成することによって行うことができます。 2番目のステップは、すべてのN個の文字列のサブシーケンスを抽出し、それらのすべてが別個であるかどうかをチェックすることによって実行できます。 しかし、このアルゴリズムは現在指数関数的に複雑です。より良いアルゴリズムが可能かどうかを知りたかったのです。

編集：いいえ、宿題ではありません。それはインタビューで尋ねられた。

Answer 1

私はこのような何かが仕事だと思う：

最初：

create matriz A (mxm) and array B(m) 
for each bit i from right to left, compute de decimal value of j word in A[i][j] 
//that means A[i][j] holds the decimal value of word j until the i bit 
in the same loop B[i] will hold if bit i from all words are the same. 

B [i]は= trueの場合、それは我々がそれは何も言うCOS、その位置を調べる必要がありいけないことを意味します。

create deque D//to check if there is equal elements 
create array C(m) 
for each position P in [0...M] where B[i] = false : 


for each bit i = P ... 0 

    for each word j 
     C[j] = C[j]*2 + word[j][i] //word[j][i] = word j in bit i 

    bool finished = true; 
    for each e in C: 
     if(D.count(e) > 0) { 
      finished = false; 
      break; 
     } 
     else{ 
      D.add(e) 
     } 
    } 
    if(finished) return range(P...i); 
    D.clear() 

not possible; 

何このアルゴリズムが行うことは次のとおりです。便利な位置から開始し、それはそれらからの単語の値の作成を開始し、瞬間に、あなたは（それらのすべてが異なる）両端キューでそれらのすべてを追加することができます、それらが異なる範囲を見つけることができます（範囲はP - i + 1サイズです）。

B [i] = falseのすべてのiに対してこれを実行しなければならないため、最悪の場合は約n³を実行する必要があります。

たとえば、文字列の数とそのサイズを知ることでできる最適化がいくつかあることに注意してください。サイズ10の文字列が10個ある場合は、区別できないことがわかります（異なる10個の異なるバイナリサイズ3）。文字列の数が指定されている場合、（連続しているかどうかにかかわらず）サイズceil（log（文字列数））だけを検索できます。例えば、5つの単語は1つのビットで異なることはできません、また、2つのビットで異なることはできませんが、3つのビットは異なることがあります。