## rabin karp

### Data

in lua

#### Tags

hashing, search, string search

### Source Code

``````-- Rabin-Karp string searching algorithm implementation
-- See: http://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_string_search_algorithm

-- Note: This implementation is based on the Python implementation of Shivam Bansal
-- See : https://github.com/kennyledet/Algorithm-Implementations/blob/master/Rabin_Karp/Python/shivam5992/rabin_karp.py

-- Rabin-Karp string searching function
-- needle   : the pattern to search
-- haystack : the string in which the pattern will be searched
-- q        : an optional prime number (internally used for hashing)
-- returns  : an array of positions of all matches found, otherwise nil
return function(needle, haystack, q)
q = q or 19
local found = {}
local d, h, flag = 256, 1, 0

local M, N = #needle, #haystack
for i = 1, M - 1 do h = (h * d) % q end

local p, t = 0, 0
for i = 1, M do
p = (d * p +   needle:sub(i, i):byte()) % q
t = (d * t + haystack:sub(i, i):byte()) % q
end

for i = 1, N - M + 1 do
if p == t then
local k = M
for j = 1, M do
if haystack:sub(i + j - 1, i + j - 1) ~= needle:sub(j, j) then break end
end
if k == M then table.insert(found, i) end
end
if i - 1 < N - M then
t = (d * (t - haystack:sub(i, i):byte() * h) + haystack:sub(i + M,i + M):byte()) % q
if t < 0 then t = t + q end
end
end

if #f > 0 then return f end
end
``````
``````-- Tests for rabin_karp.lua
local rabin_karp = require 'rabin_karp'

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

local function same(t, b)
if #t ~= #b then return false end
for k,v in ipairs(t) do
if b[k] ~= v then return false end
end
return true
end

run('Testing Rabin_Karp', function()
assert(same(rabin_karp('abcde', 'abcabcdabcde'),{8}))
assert(same(rabin_karp('t', 'test'),{1,4}))
assert(same(rabin_karp('lua', 'lua lua lua lu lua'), {1,5,9,16}))
end)

run('Can also take an optional prime number for hashing Rabin_Karp', function()
assert(same(rabin_karp('abcde', 'abcabcdabcde',23),{8}))
assert(same(rabin_karp('t', 'test',13),{1,4}))
assert(same(rabin_karp('lua', 'lua lua lua lu lua',19), {1,5,9,16}))
end)

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