Haskell 似乎工作正常，但事实并非如此

Question

这是我对 Rabin Karp 算法的实现。看起来它基本上适用于所有事情。例如:

rabinKarp“安德鲁”“德鲁”= true

rabinKarp“安德鲁”az“= false

所以这很好，但是，当我这样做时出于一些奇怪的原因”

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

Answer 1

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

您遇到了哈希冲突。所有哈希函数都存在哈希冲突的可能性，但像序数之和这样简单的哈希函数就有相当多的冲突。

当你有匹配的哈希值时，你仍然需要比较字符串来检查是否确实匹配或冲突。