boyer moore horspool


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

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)))