arrays - 如何快速找到匹配的字符串？

Question

我正在使用 Lua ——仅供引用，因此在 10^10 位数字之后，比较将变得无效 IIRC。

我有一个包含 50,000 个名字的列表——这个列表甚至可能会增加到数十万个。我试图实现显示在搜索栏中输入的部分名称的潜在匹配列表，因此如果我输入“And”，这些可能会弹出:

“安迪”“安德鲁”“安德烈”等等，一次最多 20 场比赛。

每个名字都是独一无二的——没有完全相同的名字。名称可以包含字母、数字、空格和句点。当代码运行时，这些名称的表/数组不会以任何方式排序。在 Lua 中，如果可能的话，当用户在搜索栏中输入名称时，如何显示实时潜在匹配项？

Answer 1

下面的简单程序对我来说效果很好。没有花哨的数据结构，只有简单的强力搜索。使用 / 启动新查询。使用.结束程序。使用 , 作为退格键。

/usr/share/dict/web2a 中的单词列表有 76205 个单词。它与 /usr/share/dict//words 也可以正常工作，其中有 235886 个单词。

local t={}
for w in io.lines"/usr/share/dict/web2a" do
    t[w]=true
end

os.execute("stty cbreak </dev/tty >/dev/tty 2>&1")
local s=""
while true do
    io.write("> ",s)
    local c=io.read(1)
    if c=="." then break end
    if c=="/" then s="" elseif c=="," then s=s:sub(1,-2) else s=s..c end
    local n=0
    print()
    for w in pairs(t) do
        if w:sub(1,#s)==s then
            n=n+1
            print(n,w)
            if n>=10 then break end
        end
    end
end
os.execute("stty -cbreak </dev/tty >/dev/tty 2>&1");