Re: [理工] [資結]-台大97-資工軟體設計核對

看板Grad-ProbAsk作者 (喔喔)時間14年前 (2010/02/03 09:46), 編輯推噓1(1推 0噓 1→)
留言2則, 2人參與, 最新討論串2/3 (看更多)
※ 引述《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
→
02/03 10:06, , 1F
喔喔~不過suffix這裡我就寫不出來了XD
02/03 10:06, 1F
推
02/14 22:38, , 2F
建樹要 O(n), 但是找不是要 O(NlgN) 嗎？
02/14 22:38, 2F
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1BQDLrFh (Grad-ProbAsk)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文：
完整討論串 (本文為第 2 之 3 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共3篇)
‣ 更多 FRAXIS 的文章
文章代碼(AID): #1BQDLrFh (Grad-ProbAsk)