f*****e
发帖数: 2992 | 1 没看懂，不过在你的提示下，我对算法作了些修改：
就是看在比较的时候看比较的部分是否overlap, 不断地比较p1至p2之间的子串，比如：
case 1: 没有到p2就比较出大小了：
CxxxCxxCxxY <- begins with p1
CxxxCxxCxxZ <- begins with p2
case 2: 有overlap，这时候以p1至p2之间的子串为period, 比如下面的CxxxCxxCxxyy
，最大suffix p1要么保持不变，要么是最后一个y_i：
CxxxCxxCxxyy_____x1_____ _____y1_____ _____y2_____ _____y3_____
CxxxCxxCxxyy _____y1_____ _____y2_____ _____y3_____
|y_i|=|CxxxCxxCxxyy|=12
y_i与pattern CxxxCxxCxxyy比较，如果y_i
i.e... 阅读全帖 |
|
w********1
发帖数: 3492 | 2 Wed, 13 Jun 2012 07:46:17 PDT
As noted by the Associated Press, the Internet Corporation for Assigned
Names and Numbers (ICANN) has published a list of nearly 2,000 applications
it has received as part of an expansion of the domain naming system that is
planned to add new suffixes, including some based on brands to allow
companies to simplify URLs for their sites and enhance their branding.
Apple is included in the list, having paid the $185,000 application fee
to request the ".apple" suffix... 阅读全帖 |
|
C***U
发帖数: 2406 | 3 The maximum suffix of a string is the lexicographically largest suffix of
the string. The maximum suffix problem is to find the maximum suffix of a
given string. Linear time algorithm required. |
|
f********g
发帖数: 157 | 4 永远不要用suffix tree!
能用suffix tree的情况，都应该考虑用suffix array。suffix tree内存消耗太大，根
本不可能处理大数据。而suffix array的binary search，O(logN)的复杂度，即便再大
的N，实际当中都可以把logN看成常数。 |
|
S******t
发帖数: 151 | 5 。。。这都被误导成啥样了
我相信没有任何Google和Facebook的面试题会用suffix tree的
当然，你如果是说建一个包含所有suffix的trie，那当我没说
trie是需要掌握的
如果谈到suffix tree那肯定是需要用线性构造算法了
那个Ukkonen算法极其复杂，完全不可能是面试难度
甚至acm/icpc题目里面我也基本没见过
如果实在很想了解这方面的一些知识
学一学suffix array我看足够了 |
|
e********3
发帖数: 229 | 6 请问如果在面试中面到需要用suffix tree的，该如何写好？一般不会要你当场写出来
吧。但是又没有一个特定的APT，要怎么写那代码呢？
还有一个就是longest repeated substring这题可以构造suffix tree解答，但是要用o
(n)构造的话一些隐式节点就无法显示，而最后要的节点可能就是隐式节点，请问这个
问题要怎么解决呢？关于suffix tree的我是看以下这个文章，不知道是不是我的理解
有偏差，望指教：http://www.if-yu.info/2010/10/3/suffix-tree.html#id7 |
|
a*u
发帖数: 97 | 7 给一个string建立suffix array，然后sort这些substrings，复杂度是多少？O(nlgn)
or O(n^2lgn)?
比如 String "bananna", size n = 7
suffix array
{
banana
anana
nana
ana
na
a
}
after sorting
{
a
ana
anana
banana
na
nana
}
for a string size n, creating the suffix array is O(n), sorting is supposed
to be O(nlgn), but I somehow feel it is O(n^2lgn), since the comparison
between two substrings are O(n).
Where did I miss? |
|
g******0
发帖数: 221 | 8 Given two strings: s1(length n),s2(length m).
Building the suffix tree of s1 takes O(n) time. To search s2 in the suffix
tree of s1 takes O(m). Why?
For example: s1: abcde, s2: e. The tree is shown below. Shouldn't the search
time be O(n)? 弱问，what did i miss? Maybe I should ask what is data
structure of the children of a node in a suffix tree? many thanks!
|(1:abcde)|leaf
tree:|
|(2:bcde)|leaf
|
|(3:cde)|leaf
|
|(4:de)|leaf
|
|(5:e)|leaf |
|
d*******l
发帖数: 338 | 9 我觉得suffix tree可以认为是把一个字符串的所有suffix放进一个trie中，并压缩掉
度为1的节点得到的结果。
所以原则上能用其中一个地方也能用另一个，差别在复杂度上。不过现实中trie还能写
写，suffix tree的O(n)实现不太可能写出来。最多也就能嘴上说说。 |
|
v***a
发帖数: 365 | 10 WC2009有篇论文有suffix array的实现，非常精简，但是要说明的话……谁能在20分钟
内教会面试官Suffix Array呢，除非他也懂……
当年算法老师花了2节课，3个小时才讲完基本的 Suffix Array，然后有一半多学生退
课了
论文：http://boj.5d6d.com/thread-3181-1-1.html
关键是论文里面的应用，都是很难的题目，
如果有公司面试考这种级别的程序，麻烦告诉我一下…… |
|
S******t
发帖数: 151 | 11 我对于这个问题的理解是最好用Aho-Corasick Algorithm而不是用Suffix Tree，Aho-
Corasick就是做多串匹配用的，实现复杂度也低很多。
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matchi
Suffix Tree的线性构造算法是非常复杂的，我的印象里面要在300行以上(以Ukkonen算
法为例)，而非线性的构造算法则毫无意义，还不如直接brute force的去匹配(比如说
CC150上的算法)。
Suffix Array的实现稍微简单一些，但是Linear Time的构造算法仍然并不好理解，我
的印象里三分法的实现复杂度应该在30-50行，而且几乎是千篇一律的模板，倍增法的
实现虽然好写一些但是复杂度就不是O(n)而是O(nlogn)的，不知道最近是不是有更好的
实现方式了，还请各位不吝指教。。。 |
|
g*****u
发帖数: 298 | 12 这说的我还好受点。。。
我在career cup上见到有人说他面试时，interviewer让他当场写出一个suffix tree，
我倍感打击。。。让我写个trie可能还行，suffix tree麻烦的多。。。 |
|
l*****a
发帖数: 559 | 13 呵呵，if you know suffix tree can be built in O(n) time, you should also
know that s2 can be found by traversing all children of the root node.
suffix
search |
|
j********x
发帖数: 2330 | 14 完全两种东西，区别太明显
当然可以把suffix看成是compact suffix trie
。。。 |
|
x*******6
发帖数: 262 | 15 我也有过这个想法。但suffix tree node可以存一个字符串啊。好像suffix tree最好
的implementation是用Ukkonen的方法，这个我还没看 |
|
e********3
发帖数: 229 | 16
node
那样的话suffix tree的构造就不止O（n）了。那这要怎么跟面试官说。
假设不管这个，那我要怎么用一个api来解这题呢？我没见过有suffix tree的api。自
己想一个又怕不严谨 |
|
C***U
发帖数: 2406 | 17 没。。。我算法课project就是suffix tree suffix array。有一些了解而已。 |
|
f*****e
发帖数: 2992 | 18 给个O(N)的。
两个指针可以搞定。a[1...n]。
p1=a; // p1保存前i个元素的最大suffix的起始位置。
p2=a+1; // 当前扫到的位置，与以p1起始的字符串进行比较，分4种情况：
1)如果*p2>*p1，then p1=p2，
2)*p1==*p2, then p1++;p2++直到遇到比*p1,*p2都大的字符*p4，就p1=p4，p2=p4+1
3)*p1==*p2, strcmp(p1,p2)<0, p1=比较后的最后一个period;
4)*p2 < *p1, p2++;
while(p2 < a + n)
{
if(*p2 > *p1) p1 = p2;
else if(*p2 == *p1){
p4 = p2;
k = p2 - p1; // length of pattern or period a[p1...p2-1]
j = 1;
// repeatedly compare with a[p1...p2-1]
while(++p4 < a ... 阅读全帖 |
|
l****i
发帖数: 396 | 19 trie 还是 suffix tree？
suffix tree是写最优的那个吗？ |
|
b****g
发帖数: 192 | 20 给定字符串T，然后从后向前扫一遍，能建立T的suffix tree。这一步我会做。
但是从后向前扫描有缺陷，那就是必须知道字符串的结尾，所以不能用于stream相关的
场合及压缩算法。
我知道有方法可以从前向后扫描，建立suffix tree。我从没做过这种算法。面试时有
人问这种算法吗？ |
|
y*****i
发帖数: 141 | 21 字典是已知的，pattern是未知的，且多个。这样是不是KMP就不如suffix tree了。每
一个新pattern都得重新搜一次。
就是做题的时候suffix tree感觉比KMP难写多了。。。 |
|
g**G
发帖数: 767 | 22 如果没理解错的话，应该是trie而不是suffix tree做
trie一般用于这种类似字典的查找，suffix tree一般用来重复查找同一个字符串的子串 |
|
l*******0
发帖数: 63 | 23 我觉得trie不太行吧？trie是找前缀的，但他这个是要找子串。比如字典里有abcd，
mcd, ncd, 然后要找所有含cd的，那trie岂不是一个都找不出来。可是如果是suffix
tree的话 难道为每一个字典里的string都建一课suffix tree？我觉得可能用那个
rolling hash比较不错。
子串 |
|
k***g
发帖数: 166 | 24 感觉许多字符串问题都可以用suffix tree解，但面试的时候会实际写怎么构造一棵
suffix tree吗？大家遇到过吗？ |
|
|
r******r
发帖数: 39 | 26 suffix tree?
words的数量最大1000左右。一个set中可能有几个sub group有不同的common suffix |
|
g*******y
发帖数: 1930 | 27 suffix tree写一周比较正常，两三天搞定很牛了，一天能搞定是大牛，
面试时间能写出来？除非你专行就是搞这个。 |
|
g*******y
发帖数: 1930 | 28 阿三吹牛你也信啊，呵呵
可能他自己连suffix tree和trie有啥区别都没搞清楚，面试最多就是让写个trie吧 |
|
a*u
发帖数: 97 | 29 是的啊，somewhat真是大牛，通读熟记了。
那里面讲是nlgn sort those suffix strings, 我看的应该是在O（n）出现之前的版本
。 |
|
P*******b
发帖数: 1001 | 30 O(n)建suffix tree的算法需要搞清楚吗？
怎么也看不太懂。
请指点
thanks |
|
M******1
发帖数: 90 | 31 用suffix tree 实现从string中找某些substring的算法 谁能给个链接或者简单实
现的思路？谢谢 |
|
J*******i
发帖数: 2162 | 32 是suffix array吗？programming pearl第15章有 |
|
g*****k
发帖数: 623 | 33 only one step to reach the leaf.
for suffix tree, the internal node provide random access, so it is constant
time to traverse the subtree along the edge "e" in this case.
search |
|
p*****u
发帖数: 310 | 34 我知道是建S和它的reverse的suffix tree，然后就不知了。显然不是直接找longest
common substring. 反例是bcdecb。网上找了半天也没找到，求指点。 |
|
i**********e
发帖数: 1145 | 35 Trie 的插入和查找是 O(N), N = 字符串的长度。
Trie 是 prefix tree 的简称。
网上有很多关于 trie 的教程，相信你可以很快就掌握。
至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。 |
|
g**********y
发帖数: 14569 | 36 实现简单的suffix tree build还是很容易的，你可以告诉面试官，Ukkonen 95年做了
个O(n)的，现在你让兄弟写，那是没戏，但我可以给你查出来。 |
|
a********1
发帖数: 750 | 37 主要是要用step＊2比较suffix
直接qsort 的复杂度是n^2 logn ， 因为sorting nlogn, 每个compare是n |
|
c*****l
发帖数: 879 | 38 suffix tree不是trie 有必要看下吧
面g的时候被问到了 然后就没有然后了。。 |
|
h****e
发帖数: 928 | 39 CareerCup书里至少就有一道题是用Suffix tree做的。
前几天刚刚看过，现在又忘记怎么写了。:( |
|
I******k
发帖数: 378 | 40 这两个可以用同样的数据结构实现吧， 感觉suffix tree就是trie的一种特殊情况，从
不同的位置开始到字符串末尾得到的substr建起来的trie. 最简单的实现下面这种就可
以了吧：
struct trieNode
{
trieNode *child[26]; // suppose only contain a-z
char *str; // characters in this node
}；
各位有什么看法？ |
|
I******k
发帖数: 378 | 41 trie同样一个node可以存一个字符串。suffix tree是一种特殊情况，应该有一些特殊
属性可以利用。wiki了一下Ukkonen algo，没看明白。 |
|
c********t
发帖数: 5706 | 42 比如会考写一个判断是否有palindrome 的codes吗？
如果会，怎么写，不会从构造suffix tree写起吧？
谢谢 |
|
c********t
发帖数: 5706 | 43 真恐怖啊
问个问题，leetcode上说找 sting中 Longest Palindromic Substring用suffix tree
需要O(NlogN),还不算上构建时间，为什么？
难道不是O(N)吗？ |
|
d**********x
发帖数: 4083 | 44 trie和suffix tree比起来还是很简单啊。。 |
|
Z**********4
发帖数: 528 | 45 trie好像还可以 suffix tree很难 |
|
S******t
发帖数: 151 | 46 Trie是好写的，面试题如果需要用suffix tree我认为就可以假定要不是面试者题目理
解错了要不就是算法想错了…… |
|
|
i***h
发帖数: 12655 | 48 有个应急办法是suffix array
不是最优，但是好写多了，ＳＴＬ很快搞定 |
|
|
y*****i
发帖数: 141 | 50 比如已知一个含有N个word的字典，现在随便给一个string，要找出所有包含这个
string作为子串的word。这种是用suffix tree来做吗？有更好写的方法吗？谢谢 |
|
