2

これが私のラビンカープアルゴリズムの実装です。基本的にはすべて問題なく動作するようです。例えば：

rabinKarp "andrew" "drew" = true

rabinKarp "andrew" az "= false

ですから、それは問題ありませんが、私がこれを行うと、奇妙な理由があります。」

ラビンカープ文字「こんにちは」「こんにちは」

trueを返します。これらの2つの単語でのみ発生するようですが、他の組み合わせでこれを実行することに遭遇したことはありません。なぜそれが起こっているのかについてのフィードバックをいただければ幸いです。

import Data.Char

hash :: String -> Int
hash [] = -1
hash (x:xs) = (ord x + (hash xs))

rabinKarp :: String -> String -> Bool
rabinKarp [] _ = False
rabinKarp mainString patternString =
    let
     hashPattern = hash patternString
     hashMain = hash (take (length patternString) mainString)
    in if hashPattern == hashMain
    then True
    else rabinKarp (drop 1 mainString) patternString
4

1 に答える 1

15 
Prelude> fromEnum 'h' + fromEnum 'i'
209
Prelude> fromEnum 'e' + fromEnum 'l'
209

ハッシュ衝突があります。ハッシュ衝突の可能性はすべてのハッシュ関数に与えられていますが、序数の合計のような単純なものはかなり多くの衝突があります。

一致するハッシュがある場合でも、文字列を比較して、実際に一致または衝突があるかどうかを確認する必要があります。

于 2012-12-18T14:21:30.207 に答える