Longest common prefix of any two strings in a list of strings

lcp.lua

-- Longest common prefix of any two strings in `strs`
local function lcp(strs)
    assert(#strs >= 2)
    local trie = {}
    local max_cp_len = 0
    local max_cp_node = trie
    for i, str in ipairs(strs) do
        local cp_len = 0
        local cp_node = trie
        while cp_len < #str do
            local b = str:byte(cp_len + 1)
            if cp_node[b] == nil then break end
            cp_node = cp_node[b]
            cp_len = cp_len + 1
        end
        if cp_len > max_cp_len then
            max_cp_len = cp_len
            max_cp_node = cp_node
        end
        local node = cp_node
        for j = cp_len + 1, #str do
            local b = str:byte(j)
            node[b] = node[b] or {}
            node = node[b]
        end
        node.idx = i
    end
    local i, j
    local function dfs_idx(node)
        if node.idx then
            if i == nil then i = node.idx
            elseif j == nil then j = node.idx end
        end
        for _, v in pairs(node) do
			if i and j then break end
            if type(v) == "table" then dfs_idx(v) end
        end
    end
    dfs_idx(max_cp_node)
    return max_cp_len, i, j
end

-- Test
do
	local len, i, j = lcp{"pack", "packing", "banana", "banana pie", "banana smoothie"}
	assert(len == #"banana " and math.min(i, j) == 4 and math.max(i, j) == 5)
end