## boyer moore horspool

### Data

in lua

#### Tags

search, string search

### Source Code

``````-- Booyer-Moore-Horspool algorithm implementation
-- See : http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

-- Finds the first occurence of a needle in a haystack
-- haystack : a string where to search
-- needle   : a substring to be search
-- Returns : the position of needle in haystack if found, otherwise nil.
return function (haystack, needle)
local n, m = #haystack, #needle
if m > n then return end
local bad_char_shift = {}

for k = 0, 255 do bad_char_shift[k] = m end
for k = 1, m-1 do bad_char_shift[needle:sub(k,k):byte()] = m - k end

local k = m
while k <= n do
local i, j = k, m
while j >= 1 and haystack:sub(i,i) == needle:sub(j,j) do
i, j = i-1, j-1
end
if j == 0 then return i+1 end
k = k + bad_char_shift[haystack:sub(k,k):byte()]
end

return nil
end``````
``````-- Tests for bmh.lua
local bmh = require 'bmh'

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Finds a substring in a string', function()
assert(bmh('a', 'b')                           == nil)
assert(bmh('a', 'a')                           ==   1)
assert(bmh('', 'a')                            == nil)
assert(bmh('hello', 'llo')                     ==   3)
assert(bmh('harry and john', 'john')           ==  11)
assert(bmh('Boyer-Moore-Horspool', 'Boyer')    ==   1)
assert(bmh('Boyer-Moore-Horspool', 'Moore')    ==   7)
assert(bmh('Boyer-Moore-Horspool', 'Horspool') ==  13)
assert(bmh('Boyer-Moore-Horspool', '-')        ==   6)
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````