local n = 10000


local text1 = ''
local text2 = ''
local result
local repeats = 100
local charcode
local answer
local ms_start, ms_end
local correct

local strsub, strbyte
    = string.sub, string.byte

math.randomseed(os.time())

--[[
* Determine the common prefix of two strings
* @param {string} text1 First string.
* @param {string} text2 Second string.
* @return {number} The number of characters common to the start of each
*    string.
--]]
function _diff_commonPrefix(text1, text2)
  -- Quick check for common null cases.
  if (#text1 == 0) or (#text2 == 0) or (strbyte(text1, 1) ~= strbyte(text2, 1))
	  then
    return 0
  end
  -- Binary search.
  local pointermin = 1
  local pointermax = math.min(#text1, #text2)
  local pointermid = pointermax
  local pointerstart = 1
  while (pointermin < pointermid) do
    if (strsub(text1, pointerstart, pointermid)
        == strsub(text2, pointerstart, pointermid)) then
      pointermin = pointermid
      pointerstart = pointermin
    else
      pointermax = pointermid
    end
    pointermid = math.floor(pointermin + (pointermax - pointermin) / 2)
  end
  return pointermid
end


-- Create a random string of 'n' letters.
while (#text1 < n) do
  charcode = math.random(32, 127)
  text1 = text1 .. string.char(charcode) .. text1
end
text1 = strsub(text1, 0, n)
--print (text1)

-- Create another random string which differs from the first by one letter inserted.
answer = math.random(1, n)
text2 = strsub(text1, 1, answer - 1) .. '\t' .. strsub(text1, answer)
--print (text2)

-- Linear search.
result = -1
sec_start = os.clock()
for x = 1, repeats do
  for i = 1, #text1 do
    if (strbyte(text1, i) ~= strbyte(text2, i)) then
      result = i
	  break
	end
  end
end
sec_end = os.clock()

if (result == answer) then
  correct = 'OK'
else
  correct = 'FAIL'
end
print ('Linear: ' .. (sec_end - sec_start) .. 's (' .. correct .. ')')

-- Binary search.
result = -1
sec_start = os.clock()
for x = 1, repeats do
  result = _diff_commonPrefix(text1, text2) + 1
end
sec_end = os.clock()

if (result == answer) then
  correct = 'OK'
else
  correct = 'FAIL'
end
print ('Binary: ' .. (sec_end - sec_start) .. 's (' .. correct .. ')')