Re: common prefix?

[Jerome Vuarand <jerome.vuarand@...>]

2009/7/17 Philippe Lhoste <PhiLho@gmx.net>:
> 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?

All the examples above use string.sub, so here is a different
approach. It unpacks strings with string.byte, and check for character
identity with the next(set, next(set))==nil construct.

function lcp(...)
	local t1,t2 = {...},{}
	for k,v in pairs(t1) do
		t2[k] = {string.byte(v, 1, #v)}
	end
	local result = {}
	local i = 0
	repeat
		i = i + 1
		-- build a set of characters at index i
		local set = {}
		for _,t in ipairs(t2) do
			-- mark out of range access with a special marker
			set[t[i] or 'end'] = true
		end
		local c = next(set)
		-- if the set has more than one element, we reached the end of lcp
		local mismatch = next(set, c)~=nil
		local strend = c=='end'
		local lcpend = mismatch or strend
		if c and not lcpend then
			result[#result+1] = c
		end
	until lcpend
	return string.char(unpack(result))
end

assert(lcp('foobarbaz', 'foobar', 'foofoo')=='foo')