推 hardcover:非常感謝 XD 06/20 18:31
※ 引述《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)