rabin karp


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

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