Re: common prefix?

[Philippe Lhoste <PhiLho@...>]

On 16/07/2009 21:03, Petite Abeille wrote:
> Does anyone has a little function to compute the common prefix of a list 
> of strings?

Perhaps not the best method, but it is an amusing approach, I think:

function CommonPrefix(list)
  if #list == 0 then return '' end
  local first = list[1]
  local SEP = '\1'
  local listLen = #list
  local cl = SEP .. table.concat(list, SEP)
  local prefix = ''
  local pLen, maxLen = 0, #first
  local bOK = false
  repeat
    pLen = pLen + 1
    prefix = string.sub(first, 1, pLen)
--~ print(pLen .. ' ' .. prefix)
    local pattern = string.rep(SEP .. prefix .. '.-', listLen)
--~ print(pattern)
    bOK = pLen <= maxLen and string.match(cl, pattern)
  until not bOK
  return string.sub(first, 1, pLen - 1)
end

print(CommonPrefix({ 'foobarbaz', 'foobar', 'foo' }))
print(CommonPrefix({ 'foo', 'foobarbaz', 'foobar', 'foorass' }))
print(CommonPrefix({ 'one' }))
print(CommonPrefix({ 'x', 'y' }))
print(CommonPrefix({  }))


I would have preferred to write:
    local pattern = SEP .. prefix .. '.-{' .. listLen .. '}'
(perhaps faster) but it is not possible in standard Lua.


--
Philippe Lhoste
--  (near) Paris -- France
--  http://Phi.Lho.free.fr
--  --  --  --  --  --  --  --  --  --  --  --  --  --