Re: [問題] ancestry problem
看板Prob_Solve (計算數學 Problem Solving)作者ledia時間17年前 (2007/06/20 17:49)推噓1(1推 0噓 0→)留言1則, 1人參與討論串3/15 (看更多)
※ 引述《hardcover (精裝版喔)》之銘言：
: : → ledia:啊 我說的 via suffix tree 是找 common ancestor 06/20 15:40
: : → ledia:你的應該是找 lowest common ancestor 的特例? 06/20 15:40
老實說, 我記得不是很清楚了 囧
很對不起上這堂課的好老師 Orz
不過如果方便的話, 我建議你可以翻一翻
Algorithms on Strings, Trees, and Sequences (Dan Gusfield)
ISBN:0521585198
這一本書
裡面第八章是 Constant-Time Lowest Common Ancestor Retrieval
事實上 "A 是否是 B 的祖先" 這個問題
也就是 "A, B 最低共同祖先是否就是 A"
裡面描述的 O(n) preprocessing, O(1) query 也符合你的要求
不過要 linear time 建 suffix-tree, 可能要把前面幾章看一看 orz
希望對你有幫助
--
有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
是比較不容易被擊倒的人。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.56
※ 編輯: ledia 來自: 140.112.30.56 (06/20 17:49)
推
06/20 18:31, , 1F
06/20 18:31, 1F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 15 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
