这是一个创建于 2348 天前的主题，其中的信息可能已经有所发展或是发生改变。
或者说，现在有一堆字符串（数量约 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 对待。
各位有什么更好的，或更简单的方法，或者建议？希望能在这里交流一下。
要实现成一个函数，因为调用的频繁，所以要考虑性能。
具体应用场合大家可以回想 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 对待。
各位有什么更好的，或更简单的方法，或者建议？希望能在这里交流一下。
 |
1
liprais 2018-07-15 21:06:30 +08:00
前缀树
|
 |
2
lhx2008 2018-07-15 21:08:45 +08:00 via Android
楼上正解，或者直接丢进数据库建索引
|
 |
3
kongque2016 OP |
 |
4
facat 2018-07-15 21:10:59 +08:00
正则表达式
|
|
5
liprais 2018-07-15 21:12:24 +08:00
@kongque2016 自己搜一下就行了，伸手党可耻
|
 |
6
haimall 2018-07-15 21:13:46 +08:00 via Android
excel 有什么 loop 函数？
|
 |
7
yanaraika 2018-07-15 22:26:47 +08:00  1
对于实际中不太长的字符串，方法 2 是最优的。前缀树空间太大
|
 |
8
wevsty 2018-07-15 22:45:31 +08:00
为什么我觉得根据你这种需求直接遍历查找是最快的。。。
排序也好，求 HASH 也好，我都不觉得会比直接遍历查找更快。。 |
 |
10
lance6716 2018-07-15 23:54:09 +08:00 via Android
此时就明白科班出身是多么重要了
|
 |
11
feverzsj 2018-07-16 00:01:29 +08:00
数据量大的话，DAWG 是最快的
|
 |
12
zhujinliang 2018-07-16 07:50:33 +08:00 via iPhone
这种情形应该用什么心里没有 B 树吗？🌚
|
 |
13
micean 2018-07-16 08:54:05 +08:00
1 楼 + 1
|
|
14
feverzsj 2018-07-16 11:21:15 +08:00
数据量中等的已排序序列，最快的方法是二分查找
|
 |
15
xuanbg 2018-08-24 08:12:08 +08:00
看起来前缀数量有限，1 楼正解
|
Select Language