1

この質問は頭の中でばかげているように聞こえ、おそらく非常に明白な何かを見落としているので、ここでお詫びします。ともかく...

さて、私は自分自身でスカラを学んでおり、学習演習として、文字列に別の小さな文字列が含まれているかどうかを判断するメソッドを実装することにしました。私が最初にしたことは、単純なバージョンを使用して、文字列の各文字に移動し、各文字が一致するかどうかを確認するために順方向にチェックを開始することでした。それはうまくいきました。次に、より効率的な方法を実装することにしました。これが私が思いついたものです（特別なケースは含まれていません）：

// return true if a is a substring of b
def is_sub(a: String, b: String) : Boolean = {
  for(i <- 0 until b.length-a.length) { // O(n-m)
    if(a.hashCode == b.substring(i,a.length+i).hashCode) return true // O(1) + O(1) + O(1)
  }
  return false
}

まず、誰かが私の仕事をチェックして、私が正しいことを確認できますか? 私はばかげた間違いをしがちです。2 番目に、私の時間計算量が正確であることを確認していただけますか。最初の 2 つは、文字列検索アルゴリズムのウィキペディアのページでこの方法が言及されていないのはなぜだと思いますか? 理論的には、これは O(nm) で、前処理スペースは必要ありません。

この問題の分析をどこで台無しにしましたか?

4

2 に答える 2

4

投稿したコードが正しいとは限りません。2 つの文字列が等しい場合、それらのハッシュ コードは同じでなければなりませんが、その逆は必ずしも真ではありません。異なる文字列であるが、同じハッシュ コードを持つ文字列のペアを見つけることができます。したがって、検索する文字列と同じハッシュ コードを持つ部分文字列が見つかった場合、関数は正しくない応答を返す可能性があります。

さらに、複雑さの分析は少し間違っています。長さ k の文字列のハッシュ コードを計算するには O(k) の時間がかかります (中途半端なハッシュ関数があると仮定します!)。これは、ループの各反復で O(n) の作業を行うことを意味します。取得した部分文字列のハッシュ コードを計算します。これを O(m) 回行うため、合計時間の複雑さは O(m - n) ではなく O(mn) になります。

ただし、あなたが行っていることは、実際には文字列のハッシュに基づいているRabin-Karp 文字列検索アルゴリズムに密接に関連しています。各反復で O(n) の作業を行うことを避けるために、アルゴリズムはローリング ハッシュ関数を使用します。この関数は、O(1) で 1 つの部分文字列から次の部分文字列に簡単に更新できます。また、現在のハッシュ コードが部分文字列のハッシュ コードと一致する場合、アルゴリズムが各文字を実際にチェックして一致することを確認するように、追加のチェックも行われます。このアルゴリズムは最悪の場合 O(mn) の時間を要しますが、平均的なケースでははるかに高速です (時間 O(m + n))。

お役に立てれば！

于 2013-05-07T17:19:12.567 に答える
0

あなたのアルゴリズムはまだO(nm)です。

パターンの長さを m、検索文字列の長さを n とします。

検索された文字列の (n - m) 位置のそれぞれで、部分文字列を作成し、そのハッシュコードを計算しています。これらはそれぞれ、m 文字を反復処理する必要があります。

複雑さは、作成したコードだけでなく、呼び出したコードにも依存します。

于 2013-05-07T17:16:07.413 に答える