Haskell似乎工作正常，但不是

這是我實現的Rabin Karp算法。它似乎基本上一切工作正常。例如：Haskell似乎工作正常，但不是

rabinKarp 「安德魯」，「畫」=真

rabinKarp 「安德魯」AZ「=假

所以這是好的，但是，對於一些奇怪的原因，當我這樣做」

rabinKarp 「你好」，「你好」

返回true。它似乎只發生在這兩個單詞上，我沒有遇到過這樣做與任何其他組合。希望反饋爲什麼會發生。

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

來源

2012-12-18 AndyOHart

在這裏你得到真正的，因爲：散列「el」= 208和散列「hi」= 208太 – 0xAX

我該如何解決它？ – AndyOHart

您可以使用更好的散列函數，例如'hash（x：xs）=（ord x + 257 *（hash xs））''。這將減少哈希衝突的次數，但仍不是100％安全。 – Landei

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

你有一個哈希衝突。對所有散列函數都給出了散列衝突的可能性，但是像序數總和這樣的簡單散列函數具有相當多的衝突。

當你有匹配的哈希，你仍然需要比較字符串來檢查你是否真的有匹配或碰撞。

來源

2012-12-18 14:21:30

Haskell似乎工作正常，但不是

回答

相關問題