※ 引述《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)