1

仍在努力尝试实现 Boyer Moore 算法。几个小时后到期，我无法让这个讨厌的轮班部分工作。如果有 1:1 匹配，它会起作用，即 boyerMoore "hello" "hello"

但它不适用于“howareyou”“are”

我几乎可以肯定我的问题在于 ifs 的 boyMoore 区域。

我很确定这是 boyerMoore 函数本身的东西，而不是 shift 方法。只是想知道我是否以正确的方式调用它，或者我是否在寻找某些东西？感谢任何帮助。也很抱歉今天问了这么多问题，只是希望这个任务结束并完成，因为它是我们的最后一个任务。

boyerMoore :: String -> String -> Bool
boyerMoore [] _ = False
boyerMoore mainString patternString =
    let 
    patternLength = (length patternString)
    position = getPosition patternString (take patternLength(mainString))
    in if (mainString == patternString)
        then True
        else
                if position > -1
                then boyerMoore (patternString) (drop position(mainString))
                else boyerMoore (patternString) (drop patternLength(mainString))

getPosition :: String -> String -> Int
getPosition [] _ = -1
getPosition mainString patternString = shift patternString mainString (length patternString)

shift :: String -> String -> Int -> Int
shift [] _ _ = -1
shift textString patternString lengthVariable =
    if (last patternString) == (last textString)
    then lengthVariable - (length patternString)
    else shift (init patternString) textString lengthVariable
4

1 回答 1

3

你的最终等式boyerMoore开始

boyerMoore mainString patternString =

但最后的递归调用都有形式

boyerMoore patternString (drop foo mainString)

我对 Boyer-Moore 的了解很生疏，但我怀疑你是否想这样交换patternString。mainString

其次，我认为您可能会将链接到的页面上的last()函数与 Haskell 的函数混淆。返回您给它的列表的最后一个元素，而last()，尽管有符号，但有两个参数：要查找的字符和要查找的模式字符串。lastlast

于 2012-12-19T09:46:08.120 回答