由买买提看人间百态
登录
首页
论坛
未名存档
话题女王
小圈子
马甲追踪
版面排名
流量曲线
水枪排名
发帖量曲线
发帖版面饼图
发帖时间柱图
关于本站
帮助
boards
本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字
访问原贴
JobHunting版
- 请问各位大牛,如何实现DAWG?
相关主题
●
面试中遇到suffix tree / trie这种题,需要自己实现吗?
●
急问,Boggle (crossword)的解题思路?
●
问问通常所说的字典dictionary都是用什么数据结构表示的?
●
电话号码是什么data type
●
字典里找子串怎么解?generalized suffix tree?
●
finds all repeated substrings in the string --- YAHOO interview question
●
fb 实习店面,第一题就来个hard的,算被黑吗?
●
请教几道经典题
●
再问一道A家的题目
●
那个 google hint words 的老题
●
一道老题但是以前的解好象都不对
●
有没有大牛总结一下trie, suffix tree, suffix array, B+ tree各自应用在哪些问题。
●
Amazon Interview Question
●
什么时候用SUFFIX TREE,什么时候用TRIE
●
有没有遇到让当场写一个suffix tree或者automaton的?
●
trie vs suffix tree
相关话题的讨论汇总
话题: trie
话题: dawg
话题: 实现
话题: 大牛
话题: 各位
进入JobHunting版参与讨论
1
(共1页)
s*******u
发帖数: 220
1
一个朋友去面G家,被问到这个问题,就是如何存储英文字典。查了一圈,应该是用
DAWG最优化,
http://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton
但是没有找到实现,各位大牛能否指点一下? 在网上找到的是说 Trie的实现,那个
简单很多
A*****i
发帖数: 3587
2
个人经验是
凡是要跑字典的东西,trie应该是首选
而且trie做自动机上面也有得天独厚的优势啊为什么不用trie?
l******e
发帖数: 54
3
wiki 里有比较 这是和 trie 很像的结构 但是它把一些 suffix 也共享里所以更省空间
说不能像 trie 那样存 auxiliary information 但是自己后来又说其实可以存数组里
【在 A*****i 的大作中提到】
: 个人经验是
: 凡是要跑字典的东西,trie应该是首选
: 而且trie做自动机上面也有得天独厚的优势啊为什么不用trie?
s*******u
发帖数: 220
4
多谢了,准备就把Trie的写法搞懂就算了。看到一个paper实现 DAWG,太复杂,没有一
个礼拜估计看不懂,呵呵
1
(共1页)
进入JobHunting版参与讨论
相关主题
●
trie vs suffix tree
●
再问一道A家的题目
●
请推荐好的快速教程关于B+, red-black tree, trie...
●
一道老题但是以前的解好象都不对
●
suffix tree有必要搞懂吗?
●
Amazon Interview Question
●
suffix tree 和 trie
●
有没有遇到让当场写一个suffix tree或者automaton的?
●
面试中遇到suffix tree / trie这种题,需要自己实现吗?
●
急问,Boggle (crossword)的解题思路?
●
问问通常所说的字典dictionary都是用什么数据结构表示的?
●
电话号码是什么data type
●
字典里找子串怎么解?generalized suffix tree?
●
finds all repeated substrings in the string --- YAHOO interview question
●
fb 实习店面,第一题就来个hard的,算被黑吗?
●
请教几道经典题
相关话题的讨论汇总
话题: trie
话题: dawg
话题: 实现
话题: 大牛
话题: 各位
未名新帖统计
// 7月16日
#
版面
帖数(主题数)
-
全站
4871 (796)
1
Military
3777 (569)
2
Stock
341 (51)
3
Joke
117 (17)
4
History
116 (3)
5
Automobile
100 (9)
6
USANews
55 (9)
7
Midlife
45 (1)
8
Headline
41 (41)
9
Dreamer
33 (13)
10
FleaMarket
32 (20)
11
Living
30 (7)
* 这里只显示发帖超过25的版面,努力灌水吧:-)
历史上的今天
faintcat妹妹看进来~~
发表于12年前.
NSC, PD 1/7/2007, EB2, ...
发表于11年前.
[FBA求购]MJVE2 758 MJVM2 ...
发表于6年前.
老生常谈,归与不归
发表于10年前.
【申请】Seattle西雅图 版版主——申请人...
发表于9年前.
宝宝出生,头骨骨折,求祝福
发表于9年前.
求推荐舒缓优美的古典音乐
发表于11年前.
百分之一的北京人上北大 中国网友愤怒(转载)
发表于10年前.
新人带狗狗Bailey来报道
发表于12年前.
全世界最有价值的运动队
发表于10年前.
请问大切诺基的质量如何
发表于6年前.
TNND,军版全是BKC
发表于15年前.
Inception
发表于12年前.
微软的有些家属可真恶心,为了卖保险脸都不要了
发表于10年前.
每周坐高铁的苦逼来说说感受吧!!
发表于9年前.