Day 109-Q2 — Patricia Trie（基数木・圧縮二分トライ）

問題

長さ $L$ の 0/1 文字列が $N$ 個与えられる（すべて相異なる）。これらを Patricia Trie（基数木、単一子の連鎖を1本の辺に圧縮した二分トライ）に格納せよ。

構築後、以下を出力せよ。

1. Patricia Trie の分岐ノード数（子を2つ持つノードの個数）
2. 続けて与えられる $Q$ 個のクエリ文字列（それぞれ長さ $L$）それぞれについて、集合内のいずれかの文字列との最大共通接頭辞長（LCP）

通常の二分トライは1ビットごとに1ノードを消費するため最悪$O(NL)$ノードを必要とするが、Patricia Trieは「子を1つしか持たないノード」を作らない設計にすることで、$N$個の相異なる文字列に対して常に分岐ノード数が $N-1$ 個に抑えられる。

入力形式

N L
s_1
s_2
...
s_N
Q
q_1
q_2
...
q_Q

制約

入出力例

3 4
1011
1010
0110
2
1001
0111

2
2
3

分岐ノード数: 根は「0...」と「1...」に分岐し（1つ目）、「1011」と「1010」は「101」まで共通のため更に分岐する（2つ目）。よって分岐ノード数=2=N-1。クエリ「1001」は「1011」「1010」のどちらとも「10」までの2文字が一致し最大LCP=2。クエリ「0111」は「0110」と「011」までの3文字が一致し最大LCP=3。

概念図: 通常のトライ vs Patricia Trie

ヒント（段階的開示）

class Node:
    def __init__(self):
        self.children = {}  # 辺のラベル(文字列) -> 子Node

def insert(root, s):
    node, i = root, 0
    while True:
        # node.children の中から先頭文字が s[i] と一致する辺を探す
        # 一致する辺がなければ、残り全部を新しい葉として追加して終了
        # 一致する辺があれば、共通接頭辞長 cp を求める
        #   cp == 辺のラベル長 なら、そのまま子ノードへ降りて continue
        #   cp < 辺のラベル長 なら、その位置で辺を分割し分岐ノードを作る
        ...

模範解答 (Python)

📋 コピーimport sys

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    strings = []
    for _ in range(n):
        strings.append(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    queries = []
    for _ in range(q):
        queries.append(data[idx]); idx += 1

    class Node:
        __slots__ = ['children']
        def __init__(self):
            self.children = {}

    root = Node()

    def insert(s):
        node = root
        i = 0
        while True:
            match_key = None
            for key in node.children:
                if key[0] == s[i]:
                    match_key = key
                    break
            if match_key is None:
                node.children[s[i:]] = Node()
                return
            key = match_key
            cp = 0
            while cp < len(key) and i + cp < len(s) and key[cp] == s[i + cp]:
                cp += 1
            if cp == len(key):
                node = node.children[key]
                i += cp
                continue
            child = node.children.pop(key)
            mid = Node()
            node.children[key[:cp]] = mid
            mid.children[key[cp:]] = child
            if i + cp < len(s):
                mid.children[s[i + cp:]] = Node()
            return

    for s in strings:
        insert(s)

    branch_count = 0
    stack = [root]
    while stack:
        node = stack.pop()
        if len(node.children) >= 2:
            branch_count += 1
        stack.extend(node.children.values())

    def max_lcp(s):
        node = root
        i = 0
        best = 0
        while True:
            match_key = None
            for key in node.children:
                if i < len(s) and key[0] == s[i]:
                    match_key = key
                    break
            if match_key is None:
                return best
            key = match_key
            cp = 0
            while cp < len(key) and i + cp < len(s) and key[cp] == s[i + cp]:
                cp += 1
            best += cp
            if cp < len(key):
                return best
            node = node.children[key]
            i += cp
            if i == len(s):
                return best

    out = [str(branch_count)]
    for qs in queries:
        out.append(str(max_lcp(qs)))
    print("\n".join(out))

solve()

Step-by-Step 解説

よくあるミス

次のステップ

• 発展: 各葉にIDを持たせ、クエリ文字列と最大LCPを達成する文字列そのものも復元できるようにする
• 発展: 挿入だけでなく削除もサポートし、削除後に分岐ノードが単一子になったら辺をマージし直す
• 発展: 整数列のXOR最大値クエリ（01-Trie応用）にPatricia Trie圧縮を組み合わせ、省メモリ実装を検討する

自己評価

自分の回答

気づき・メモ