Day 131-Q3 — McCreightのアルゴリズム（サフィックスツリー構築）

2026-08-23 赤色 Master / Phase 8+ ★★★★★★★★★ 辺ラベル長総和=相異なる部分文字列数

問題

文字列$S$（小文字英字のみ）が与えられる。$S$に含まれる相異なる（空でない）部分文字列の個数を求めよ。

入力形式

S

制約

$1 \le |S| \le 2000$
$S$は小文字英字のみ

入出力例

入力例1

banana

出力例1

15

入力例2

aabaa

出力例2

11

概念図

長い接尾辞から順に挿入し、辺を分割しながら木を育てる root "ba..." "a" "nana" "$leaf" 葉ノードだけでなく「辺の途中の点」も含めた根からのパスが相異なる部分文字列に1対1対応 → 全辺のラベル長の総和 = 相異なる部分文字列数

ヒント（段階的開示）

ヒント1（方向性）

全部分文字列をsetに入れれば求まるがO(N²)個作ることになる。もっと構造的に数える道具がサフィックスツリー。全接尾辞を根から並べた圧縮トライにおいて、根から任意の点（辺の途中も含む）までのパスがちょうど1つの相異なる部分文字列に対応する。

ヒント2（アプローチ）

愚直に1接尾辞ずつ根から挿入するとO(N²)。McCreightのアルゴリズムは直前に挿入した接尾辞のサフィックスリンク（1文字短い接尾辞に対応するノード）を使い、根からではなくその近傍から探索を再開して高速化する。教育目的の実装ではこの「長い接尾辞から順に挿入する」骨格を保ちつつ、サフィックスリンクによる高速化を省略しても同じ木構造が得られる。

ヒント3（誘導） 
def insert_suffix(root, suf):
    node = root
    i = 0
    while i < len(suf):
        c = suf[i]
        if c not in node.children:
            # 新しい葉を生やして終わり
            ...
            return
        label, child = node.children[c]
        # label と suf[i:] の共通接頭辞長 j を求め
        # j==len(label) なら降りる、j<len(label) なら辺を分割する

模範解答 (Python)

import sys


class Node:
    __slots__ = ("children",)
    def __init__(self):
        self.children = {}  # 先頭文字 -> (edge_label:str, child_node)


def insert_suffix(root, suf):
    node = root
    i, n = 0, len(suf)
    while i < n:
        c = suf[i]
        if c not in node.children:
            node.children[c] = (suf[i:], Node())
            return
        label, child = node.children[c]
        j, L = 0, len(label)
        while j < L and i + j < n and label[j] == suf[i + j]:
            j += 1
        if j == L:
            node = child
            i += j
            continue
        # 辺を位置jで分割する
        mid = Node()
        mid.children[label[j]] = (label[j:], child)
        remaining = suf[i + j:]
        if remaining:
            mid.children[remaining[0]] = (remaining, Node())
        node.children[c] = (label[:j], mid)
        return


def build_suffix_tree(s):
    root = Node()
    for i in range(len(s)):        # 長い接尾辞から順に挿入（McCreight型の順序）
        insert_suffix(root, s[i:])
    return root


def count_distinct_substrings(root):
    total = 0
    stack = [root]
    while stack:
        node = stack.pop()
        for label, child in node.children.values():
            total += len(label)
            stack.append(child)
    return total


def solve():
    s = sys.stdin.readline().strip()
    root = build_suffix_tree(s)
    print(count_distinct_substrings(root))


solve()

Step-by-Step 解説

1接尾辞を長い順に挿入する
S[0:],S[1:],...,S[N-1:]を長い方から順に圧縮トライへ挿入する。McCreightがこの順序を採るのは、長い接尾辞を先に骨格として作ると後続の短い接尾辞はサフィックスリンク経由で高速に処理できるため。
2辺の分割(edge split)
挿入中の残り部分と既存の辺ラベルを先頭から比較し、一致長jを求める。jが辺ラベル全体と一致すれば子へ降りる。途中で不一致ならその位置で辺を中間ノードで分割し新しい葉を生やす。
3辺ラベル長の総和=相異なる部分文字列数
サフィックスツリーの根からの各パス文字列は部分文字列に対応し、異なるパスは異なる文字列になる。よって辺ラベル長の総和を数えれば相異なる部分文字列数と一致する。
4終端記号$が不要な理由
$は「ある接尾辞が別の接尾辞の接頭辞になる曖昧さ」を解消するために使われるが、本問では葉ノードを明示管理する必要がなく、単に既存の子がなければ新しい葉を作る処理だけで曖昧さなく構築できる。
5計算量
真のMcCreightはサフィックスリンク+fast/slowスキャンでO(N)（アルファベット定数時）を達成する。本実装は高速化を省略した素朴な挿入で最悪O(N²)だが、N≤2000なら十分高速。

よくあるミス

ミス原因正しい書き方
接尾辞を短い順に挿入する挿入順序が結果に影響しないと誤解する木の最終形は同じになるが、McCreight本来の高速化は「長い順」が前提なので学習上はこの順序で実装する
辺分割時に元の子ノードの接続を忘れる分割後、中間ノードから元の子への辺ラベル更新を忘れるmid.children[label[j]] = (label[j:], child) のように残り部分を正しく繋ぎ直す
空文字列を1個の部分文字列として数える「相異なる部分文字列」の定義を誤解する空文字列は除外し、辺ラベル長の総和(根自体は数えない)だけを答えとする
親ノードの辞書のキーが分割前後で2つ残る分割後に親のchildren更新で上書きし忘れるnode.children[c] = (label[:j], mid) で親のキーcを新しい辺で上書きすることを徹底する

次のステップ

  • 発展: サフィックスリンクを実際に構築・利用してskip/countトリックによる真のO(N)挿入を実装する
  • 次回予告: 次回のテーマは今後のセッションで選定

自己評価

自分の回答

気づき・メモ