A radix trie

trie.lua

local Trie = {}
Trie.__index = Trie

function Trie:__tostring()
    return "Trie"
 end

function Trie:__call(...)
  local obj = setmetatable({}, self)
  obj:new(...)
  return obj
 end

function Trie:new()
  self.children = {}
  self.root = true
  self.prefix_cache = {}
end

function Trie:traverse(str)
  local node = self
  local last, next
  local i, l = 0, #str
  while node and i < l do
    next = nil
    for _, child in ipairs(node.children) do
      local j = (str:find(child.data, i + 1, true) or i) - i
      if j == 1 then
        next = child
        break
      end
    end

    last = node
    if next then
      node = next
      i = i + #next.data
    else
      node = nil
    end
  end
  
  return node, i, l, last
end

function Trie:text_from_node(node)
  if not self.prefix_cache[node] then
    local text, i = {}, -1
    while node and node ~= self do
      text[i] = node.data
      node = node.parent
      i = i - 1
    end
    text = table.concat(text, "", i + 1, -1)
    self.prefix_cache[node] = text
  end
  return self.prefix_cache[node]
end

function Trie:suggest(str, max_result)
  max_result = max_result or 10
  
  local node, i, l, last = self:traverse(str)
  local result = {}

  -- bfs the last node
  local visit = { node or last }
  while #visit > 0 do
    node = table.remove(visit)
    
    for _, child in ipairs(node.children) do
      if #child.children > 0 then
        table.insert(visit, child)
      end
      if #result <= max_result then
        table.insert(result, self:text_from_node(child))
      else
        return result
      end
    end
  end
  return result
end

function Trie:insert(str)
  local _, i, _, last = self:traverse(str)
  table.insert(last.children, {
    parent = last,
    children = {},
    data = str:sub(i + 1)
  })
end

function Trie:lookup(str)
  local node, i, l = self:traverse(str)
  return not not (node and i == l)
end