knuth morris pratt


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Tags

Source Code

-- Knuth-Morris-Pratt string searching algorithm implementation
-- See: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

local function kmp_table(pattern)
  local result = {}
  for i = 1, #pattern+1,1 do
    local j = i
    while true do
      if j == 1 then
        result[#result + 1] = 1
        break
      end
      j = j-1
      if pattern:sub(result[j], result[j]) == pattern:sub(i, i) then
        result[#result + 1] = result[j] + 1
        break
      end
      j = result[j]
    end
  end
  return result
end

-- Knuth-Morris-Pratt string searching function
-- needle   : the pattern to search
-- haystack : the string in which the pattern will be searched
-- returns  : the position of the match, otherwise nil
return function(needle, haystack)
  local fail = kmp_table(needle)
  local index, match = 0,1
  while index + match < #haystack do
   if haystack:sub(index + match, index + match) == needle:sub(match, match) then
      match = match + 1
      if match-1 == #needle then
        return index
      end
    else
      if match == 1 then index = index + 1
      else
        index = index + match - (fail[match-1])
        match = fail[match-1]
      end
    end
  end
end
-- Tests for kmp.lua
local kmp = require 'kmp'

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('Testing Knuth_Morris_Pratt', function()
  assert(kmp('ABCDABD', 'ABC ABCDAB ABCDABCDABDE'),           15)
  assert(kmp('0101', '0011001011'),                            5)
  assert(kmp('lu lu lu lua lu', 'alualu lu lu lua lus'), 4)
end)

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