suffix tree 和 trie - JobHunting版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - suffix tree 和 trie

相关主题
● 问个Longest Common Substring的问题	● word search follow up的问题
● 请教几道经典题	● 被烙印阴了： draw a line across two points
● 什么时候用SUFFIX TREE，什么时候用TRIE	● 攒人品，分享Pinterest面经
● suffix tree有必要搞懂吗？	● 面试的时候用到Trie，要求实现吗？
● 面试中遇到suffix tree / trie这种题，需要自己实现吗？	● 最近好几个trie的面试题，有人愿意分享一下trie到底怎么implement的吗？
● finds all repeated substrings in the string --- YAHOO interview question	● FB面试题一道求解
● Amazon Interview Question	● google 电面fast phone book loopup
● on-site的时候Trie和suffix tree会考coding吗？	● 问一道面试设计题

相关话题的讨论汇总
话题: suffix话题: trie话题: tree话题: trienode话题: 字符串

进入JobHunting版参与讨论

1

(共1页)

I******k 发帖数: 378	1 这两个可以用同样的数据结构实现吧，感觉suffix tree就是trie的一种特殊情况，从不同的位置开始到字符串末尾得到的substr建起来的trie. 最简单的实现下面这种就可以了吧： struct trieNode { trieNode child[26]; // suppose only contain a-z char str; // characters in this node }；各位有什么看法？
x*******6 发帖数: 262	2 我也有过这个想法。但suffix tree node可以存一个字符串啊。好像suffix tree最好的implementation是用Ukkonen的方法，这个我还没看
I******k 发帖数: 378	3 trie同样一个node可以存一个字符串。suffix tree是一种特殊情况，应该有一些特殊属性可以利用。wiki了一下Ukkonen algo，没看明白。【在 x*******6 的大作中提到】 : 我也有过这个想法。但suffix tree node可以存一个字符串啊。好像suffix tree最好 : 的implementation是用Ukkonen的方法，这个我还没看

1

(共1页)

进入JobHunting版参与讨论

相关主题
● 问一道面试设计题	● 面试中遇到suffix tree / trie这种题，需要自己实现吗？
● design search engine typeahead的问题	● finds all repeated substrings in the string --- YAHOO interview question
● 一道老题但是以前的解好象都不对	● Amazon Interview Question
● 攒rp整理面试题(1)string match/text search	● on-site的时候Trie和suffix tree会考coding吗？
● 问个Longest Common Substring的问题	● word search follow up的问题
● 请教几道经典题	● 被烙印阴了： draw a line across two points
● 什么时候用SUFFIX TREE，什么时候用TRIE	● 攒人品，分享Pinterest面经
● suffix tree有必要搞懂吗？	● 面试的时候用到Trie，要求实现吗？

相关话题的讨论汇总
话题: suffix话题: trie话题: tree话题: trienode话题: 字符串

未名新帖统计// 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的版面，努力灌水吧:-)