順序木の右枝分解
ref. 『部分語計数問題の接尾辞配列を用いた高速アルゴリズム』PDF
明示的に接尾辞木を構築することなく接尾辞木の深さ優先、帰りがけ順での全探索を実現する
この「木を明示的に構築することなく」が重要
既に木が構築されてるなら素直に探索すれば良いだけなので。
論文では後置順巡回と呼んでる
二頂点の親子関係と、隣り合う葉との最近共通先祖が与えられるなら後置順巡回ができる
接尾辞配列の場合「開始点と長さの対」で木の頂点が表現できる
葉は文字列末までの長さを持つ
wがvの先祖であるならば、wの長さがvよりも小さい
逆は必ずしも真ではないけど、最近共通祖先との間での比較しかしないのでOK
最近共通先祖は長さをLCP arrayであらかじめ計算しておいたものに変えれば得られる
論文では「高さ」と表現されている
いわゆる木の高さなどとは関係ない
pythondef test_travase_tree():
"""
>>> test_travase_tree()
[6, 1]
* 1
[6]
[6, 3]
[6, 3, 2]
* 2
[6, 3]
* 3
[6]
[6, 5]
[6, 5, 4]
* 4
[6, 5]
* 5
[6]
* 6
[]
"""
ROOT = 0
TOP = 6
parent = [TOP, 3, 3, 5, 5, 0, TOP]
leafs = [1, 2, 4]
stack = [TOP]
nearest_common_ancestors = [None, 3, 5, None, 6, None]
def is_ancestor_of(anc, x):
while True:
x = parent[x]
if x == anc:
return True
if x == 6:
return False
for leaf in leafs:
stack.append(leaf)
print(stack)
v = stack[-1]
w = nearest_common_ancestors[leaf]
while is_ancestor_of(w, v):
print("*", v)
stack.pop()
print(stack)
if not stack:
return
v = stack[-1]
if v != w and is_ancestor_of(v, w):
stack.append(w)
print(stack)Related Pages
- →atcoder×atcoder_library_practice_contest×numba×cython×フェニック木×セグメント木×遅延伝搬セグメント木×接尾辞配列×LCP array×pythonでの累乗・逆数・階乗・階乗逆数・組み合わせ×中国剰余定理×floor_sum×np.convolve×two_snuke×長整数が速い×dsu×unionfind×最大流×最小費用流×scc×2-sat→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]