推 fenzhang: O(n)屬於O(nlogn),就像不會因為n<5就說n<6是false 02/12 01:37
※ 引述《FRAXIS (喔喔)》之銘言：
: ※ 引述《taitin (小南)》之銘言：
: : 7. 好像是用suffix之類的方法解...
: 建立Suffix Tree
: 可以想像是把兩個字串的所有Suffix String塞進一個Trie
: 這樣如果有共同的substring，那他們在Trie中必定會共享Internal Node，
: 自然就偵測的出來，也可以找的出最長的substring。
: 建立Suffix Tree需要O(n)的時間（非常複雜的演算法）
: 要找出longest common substring也需要O(n)。
想請問97台大資工DS最後一題
我看演算法筆記也是說O(n)可以處理
所以開頭寫法應該要寫disprove, because it can be solved in O(n) time
再開始寫algo嗎? (但bounded在O(nlogn) 好像也不違反~""~ 直接寫是不是也可以)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.229.1.34
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1454820769.A.4CA.html