CODEWITHSUNDEEP
haskell
Ayohaych
Ayohaych

Reputation: 5189

Haskell seems to work fine but isn't

Here is my implementation of the Rabin Karp algorithm. It seems like it works fine for basically everything. For example:

rabinKarp "andrew" "drew" = true

rabinKarp "andrew "az" = false

So that is fine, however, for some odd reason when I do this"

rabinKarp "hello" "hi"

it returns true. It only seems to happen on these 2 words, I haven't ran into it doing this with any other combination. Would appreciate any feed back as to why it's happening.

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

Upvotes: 2

Views: 191

Answers (1)

Daniel Fischer
Daniel Fischer

Reputation: 183873

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

You have a hash collision. The possibility of a hash collision is given for all hash functions, but such a simple one as the sum of the ordinal numbers has quite a lot of collisions.

When you have matching hashes, you still need to compare the strings to check whether you really have a match or a collision.

Upvotes: 15

Related Questions