問題は、与えられた DNA 配列で複数回出現する長さ k のすべての配列を見つけることです。長さ k の各シーケンスについて、ハッシュが計算され、マップに格納される、ローリング ハッシュ関数を使用するアプローチを見つけました。現在のシーケンスが繰り返しかどうかを確認するには、そのハッシュを計算し、ハッシュがハッシュ マップに既に存在するかどうかを確認します。はいの場合は、このシーケンスを結果に含めます。そうでない場合は、ハッシュ マップに追加します。
ここでのローリング ハッシュとは、ウィンドウを 1 つスライドさせて次のシーケンスに移動するときに、前のシーケンスの最初の文字の寄与を削除し、新しく追加された文字の寄与を追加する方法で、前のシーケンスのハッシュを使用することを意味します。つまり、新しいシーケンスの最後の文字です。
Input: AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT
and k=10
Answer: {AAAAACCCCC, CCCCCAAAAA}
このアルゴリズムは完璧に見えますが、完全なハッシュ関数を作成して衝突を回避することはできません。誰かがどのような状況でも完璧なハッシュを作成する方法を説明できれば、それは大きな助けになります.