haskell - Haskell 似乎工作正常，但不是

Question

这是我对 Rabin Karp 算法的实现。似乎它基本上适用于所有事情。例如：

拉宾卡普“安德鲁”“画”=真

拉宾卡普“安德鲁”阿兹“=假

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

拉宾卡普“你好”“嗨”

它返回真。它似乎只发生在这两个词上，我还没有遇到任何其他组合。将不胜感激任何反馈，为什么它会发生。

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

你有一个哈希冲突。所有散列函数都存在散列冲突的可能性，但是像序数之和这样简单的函数有相当多的冲突。

当您有匹配的哈希时，您仍然需要比较字符串以检查您是否真的有匹配或冲突。