正確に一つの位置で異なる配列の全ての対

Question

Iは、次の非標準の動作と（同一の、既知の長さの全て）シーケンスのセットを表すデータ構造を必要とする検索：

2検索を正確に1つのインデックスで異なるセット内のシーケンス。 （または、そのようなペアが存在しないことを確立する。）

Nは配列と配列のM数の長さであれば、明らかO(N*M*M)アルゴリズムがあります。これをより効率的に解決するための標準的な方法があるのだろうかと思います。必要に応じて前処理を適用したいと思います。

ボーナスは、ペアを返す代わりに、同じポイントで異なるすべてのシーケンスを返します。

あるいはは、また、私は特定配列がセット中の任意の配列からで一つのインデックスで異なるかどうかを効率的に確認することができ、溶液中の興味。それが助けになるならば、セットでは、2つのシーケンスがそのプロパティを持たないと仮定することができます。

編集：あなたはNをかなり小さくすることができます。これにより、私は改善のためのO(log(N)*M*M)のようなものは、私の使用事例にすぐには役立たないということです。

Answer 1

各シーケンスとそのシーケンス内の各ポジションiについて、ポジションiのないシーケンスのハッシュを計算し、それをハッシュテーブルに追加します。すでにテーブルにエントリがある場合は、1つの位置だけが異なる可能性のあるペアが見つかりました。開始と終了の両方からrolling hashesを使用してそれらを結合すると、一定の時間内に各ハッシュを計算できます。総稼働時間はO（N * M）と予想されます。

Answer 2

k個のインデックスをランダムに選択します（重複しないようにしてください）。

各セットに対して、要素をXORします。

これで、ドキュメントごとにj本の指紋があります。

これらのフィンガープリントに基づいてシーケンスを比較します。 j-1個の指紋は、シーケンスが実際に一致する場合に一致しなければならない。しかし逆は真実ではないかもしれませんし、あなたは場所によって場所を確認しなければならないかもしれません。

比較部分の詳細説明：すべてのドキュメントからすべてのフィンガープリントをソートします（またはハッシュテーブルを使用します）。そうすれば、すべてのペアを比較する必要はなく、一致する指紋を持つペアだけを比較することができます。

Answer 3

単純な再帰的なアプローチ：

• は、ソートやハッシュを通じて同じ前半を有する配列のすべてのセットを検索します。

• これらのセットのそれぞれについて、今度は後半を見るだけで全体のプロセスを繰り返します。

• ソートまたはハッシュを通して同じ後半を持つすべてのシーケンスのセットを検索します。

• これらのセットのそれぞれについて、全体の処理を今度は最初の半分だけ見るようにします。

• 長さが1になると、一致しないものがすべてあなたの探しているものになります。

擬似コード：

findPairs(1, N) 

findPairs(set, start, end) 
    mid = (start + end)/2 
    sort set according to start and mid indices 
    if end - start == 1 
    last = '' 
    for each seq: set 
     if last != '' and seq != last 
     DONE - PAIR FOUND 
     last = seq 
    else 
    newSet = {} 
    last = '' 
    for each seq: set 
     if newSet.length > 1 and seq and last don't match from start to mid indices 
     findPairs(newSet, mid, end) 
     newSet = {} 
     newSet += seq 
     last = seq 

すべてのペアを見つけることができるようにコードを変更するのに十分な簡単なはずです。

複雑さ？私は間違っているかもしれませんが、

最大深度はlog Mです。 （私は信じています）最悪の場合は、すべての配列が同一である場合です。この場合、実行される作業はO(N*M*log M*log M)となり、これはO(N*M*M)よりも優れています。