Lua前缀树：词库的前缀检索结构

-- 错误：每敲一键全表线性过滤
function suggest(prefix)
    local out = {}
    for _, w in ipairs(WORDS) do
        if w:find(prefix, 1, true) == 1 then
            out[#out + 1] = w
        end
    end
    return out
end

local root = {}
local function insert(word)
    local node = root
    for ch in word:gmatch(".") do
        node.children = node.children or {}
        node.children[ch] = node.children[ch] or {}
        node = node.children[ch]
    end
    node.leaf = true
end
local function findNode(prefix)
    local node = root
    for ch in prefix:gmatch(".") do
        node = node.children and node.children[ch]
        if node == nil then return nil end
    end
    return node
end