順序木の右枝分解

• ref. 『部分語計数問題の接尾辞配列を用いた高速アルゴリズム』PDF

• 明示的に接尾辞木を構築することなく接尾辞木の深さ優先、帰りがけ順での全探索を実現する

  • この「木を明示的に構築することなく」が重要
  • 既に木が構築されてるなら素直に探索すれば良いだけなので。
  • 論文では後置順巡回と呼んでる

• 二頂点の親子関係と、隣り合う葉との最近共通先祖が与えられるなら後置順巡回ができる

  • 接尾辞配列の場合「開始点と長さの対」で木の頂点が表現できる
    • 葉は文字列末までの長さを持つ
    • wがvの先祖であるならば、wの長さがvよりも小さい
      • 逆は必ずしも真ではないけど、最近共通祖先との間での比較しかしないのでOK
    • 最近共通先祖は長さをLCP arrayであらかじめ計算しておいたものに変えれば得られる
      • 論文では「高さ」と表現されている
        • いわゆる木の高さなどとは関係ない

python

def 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)