作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [资结]-台大97-资工软体设计核对
时间Wed Feb 3 09:46:27 2010
※ 引述《taitin (小南)》之铭言：
: 7. 好像是用suffix之类的方法解...
建立Suffix Tree
可以想像是把两个字串的所有Suffix String塞进一个Trie
这样如果有共同的substring，那他们在Trie中必定会共享Internal Node，
自然就侦测的出来，也可以找的出最长的substring。
建立Suffix Tree需要O(n)的时间（非常复杂的演算法）
要找出longest common substring也需要O(n)。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：→ taitin:喔喔~不过suffix这里我就写不出来了XD 02/03 10:06
2F：推 leeheng:建树要 O(n), 但是找不是要 O(NlgN) 吗？ 02/14 22:38