分享一盗题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

分享一盗题

分享一盗题# JobHunting - 待字闺中

s*82014-10-10 07:10

1 楼

有很多字串，经常要作的操作有，插入，删除，清空，
查询以某前缀字串开头的所有的字串
查询以某前缀字串开头的所有的字串的个数
查询前缀字串开头的字串的所有可能的下一个字母
例如
[abc, abd, abe]
input ab
return [c, d, e]
要求使3个查寻操作的时间上最优，插入，删除，清空，的性能表现可以牺牲
那种数据结构实现比较好。

l*a2014-10-10 07:10

2 楼

这个需要查吗?
Trie

【在 s*******8 的大作中提到】

: 有很多字串，经常要作的操作有，插入，删除，清空，
: 查询以某前缀字串开头的所有的字串
: 查询以某前缀字串开头的所有的字串的个数
: 查询前缀字串开头的字串的所有可能的下一个字母
: 例如
: [abc, abd, abe]
: input ab
: return [c, d, e]
: 要求使3个查寻操作的时间上最优，插入，删除，清空，的性能表现可以牺牲
: 那种数据结构实现比较好。

p*22014-10-10 07:10

3 楼

这么勤奋？

【在 l*****a 的大作中提到】

:
: 这个需要查吗?
: Trie

s*82014-10-10 07:10

4 楼

如果这么简单，我就不问了，我实现的就trie, 有人说可以用 STL现成的container

【在 l*****a 的大作中提到】

:
: 这个需要查吗?
: Trie

s*82014-10-10 07:10

5 楼

没有说清除，要查询的是前缀字串开头的字串的所有可能的下一个字母
例如
[abc, abd, abe]
input ab
return [c, d, e]

【在 l*****a 的大作中提到】

:
: 这个需要查吗?
: Trie

M*p2014-10-10 07:10

6 楼

好

：有很多字串，经常要作的操作有，插入，删除，清空，
：查询以某前缀字串开头的所有的字串

l*a2014-10-10 07:10

7 楼

这个用trie不work吗?

【在 s*******8 的大作中提到】

: 没有说清除，要查询的是前缀字串开头的字串的所有可能的下一个字母
: 例如
: [abc, abd, abe]
: input ab
: return [c, d, e]

s*82014-10-10 07:10

8 楼

work 阿，
这个查询用trie很容易实现，直接遍历子指针，都不用递归，或者DFS
但是我的意思是如果不用 trie,怎么实现。。。

【在 l*****a 的大作中提到】

: 这个用trie不work吗?

l*a2014-10-10 07:10

9 楼

你问"茴"子的四种写法?

【在 s*******8 的大作中提到】

: work 阿，
: 这个查询用trie很容易实现，直接遍历子指针，都不用递归，或者DFS
: 但是我的意思是如果不用 trie,怎么实现。。。

s*82014-10-10 07:10

10 楼

不是我非要问茴字，是有人问除了trie，能不能直接用STL的某个container

【在 l*****a 的大作中提到】

: 你问"茴"子的四种写法?

Q*F2014-10-10 07:10

11 楼

插入，删除，清空，的性能表现可以牺牲的话，是不是用2个map比较好？
任何插入的string，用它所有的前缀做成这两个map的key
一个map的value用一个vector记录所有以该key为前缀的字符串，这个主要用来做1，2
的操作，另外一个map的value用一个26位长的数组来记录下一个字符及个数，这个用
来做3的操
作。
当删除一个字符串的时候，根据字符串的所有前缀删除第一个map中所有的该字符串。
第二个map的中含有该字符串的前缀的下一个字符的个数减少1
当然，这样会用到巨量空间。如果改用指针的话是不是会节约空间。
map > map1
map > map2;

s*82014-10-10 07:10

12 楼

恩，这个可以，就是浪费空间。每一个长度为N的字串，都要2N个 map entry

2

【在 Q**F 的大作中提到】

: 插入，删除，清空，的性能表现可以牺牲的话，是不是用2个map比较好？
: 任何插入的string，用它所有的前缀做成这两个map的key
: 一个map的value用一个vector记录所有以该key为前缀的字符串，这个主要用来做1，2
: 的操作，另外一个map的value用一个26位长的数组来记录下一个字符及个数，这个用
: 来做3的操
: 作。
: 当删除一个字符串的时候，根据字符串的所有前缀删除第一个map中所有的该字符串。
: 第二个map的中含有该字符串的前缀的下一个字符的个数减少1
: 当然，这样会用到巨量空间。如果改用指针的话是不是会节约空间。
: map > map1