频繁从一堆 string 里查找特定前缀的字符串，大家有什么快速算法吗？

[kongque2016]

或者说，现在有一堆字符串（数量约 1000 ），随意给定前几个字符，例如"abc",要求找出所有以"abc"开头的字符串。
要实现成一个函数，因为调用的频繁，所以要考虑性能。
具体应用场合大家可以回想 vim 状态栏按冒号然后上 /下翻找历史命令时，它会根据已输入的补全。
我目前想到两个方法，方法一：
把这些字符串排序存储。例如排序成这样:
abc
abcd
bcd
bce
bceaaa
begggggg
c
df

排序算法是：按首字母逐渐往后比较。
查找方法是简单的线性查找
再跟大家确认一下函数的功能，例如：
接受"ab"，要返回"abc", "abcd"；
接受“ bce"，要返回"bce","bceaaa"；


方法二：
设置 10 个哈希表，对所有字符串手动做 hash，从第一个字母开始，hash 算法每推进一个字符，就把当前的 hash 值存到对应的哈希表。
这样，以后查找"abc"时，直接从第三个("abc"的 strlen 是 3)哈希表取出 hash 值对应"abc"的所有字符串，再做一下 strncmp()就行了。
设置了 10 个哈希表，如果 10 个以后还区分不出，就另行存储，按方法 1 对待。

各位有什么更好的，或更简单的方法，或者建议？希望能在这里交流一下。

[liprais]

前缀树

[lhx2008]

楼上正解，或者直接丢进数据库建索引

[kongque2016]

@liprais @lhx2008
如果用 C 语言实现的话，有什么好的方法？

[facat]

正则表达式

[liprais]

@kongque2016 自己搜一下就行了，伸手党可耻

[haimall]

excel 有什么 loop 函数？

[yanaraika]

对于实际中不太长的字符串，方法 2 是最优的。前缀树空间太大

[wevsty]

为什么我觉得根据你这种需求直接遍历查找是最快的。。。
排序也好，求 HASH 也好，我都不觉得会比直接遍历查找更快。。

[MIMEIK]

@wevsty 前缀短的话感觉直接比不错，比较长的前缀就有点尴尬了，看楼主的需求了。

[lance6716]

此时就明白科班出身是多么重要了

[feverzsj]

数据量大的话，DAWG 是最快的

[zhujinliang]

这种情形应该用什么心里没有 B 树吗？🌚

[micean]

1 楼 + 1

[feverzsj]

数据量中等的已排序序列，最快的方法是二分查找

[xuanbg]

看起来前缀数量有限，1 楼正解