Posts

Template. KMP

KMP字串比對,回傳第一組子字串的位置。 若失敗則回傳-1。
2018-08-16

Template. Heavy-light Decomposition

第一次DFS,son():先紀錄所有點的子節點(含)數目、深度等資訊。 第二次DFS,build():依據上次DFS的結果,優先選擇子節點最多的點構成重鏈。
2018-08-15

Template. LCA Doubling Search

使用倍增法的做法來計算LCA。 先製作dp表,$dp[i][j]$代表$i$的第$2^j$祖先是誰,若不存在則為-1。 在查詢時,先將點$a$和$b$調整到相同高度,再一起慢慢往上移動尋找LCA。 時間複雜度:$O(N log N)$
2018-08-15