请问各位大牛，如何实现DAWG? - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示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的版面，努力灌水吧:-)