## knuth morris pratt

in lua

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