Trieで共有接頭辞を索引化する
概要
Trieによる共有接頭辞の索引
文字列集合の各文字遷移を木として共有し、prefix通過数・prefix DP・辞書順探索をnode上で処理する。
考え方
共通prefixを一度だけ保存する根付き木がTrieである。根からの経路が文字列を表し、節点にはそのprefixを持つ文字列の個数や終端数を置く。比較を文字単位の枝選択へ移すことで、文字列全体の繰り返し比較を避ける。
rootの通過数と終端数を0で初期化する。文字列を挿入するときrootの通過数を一増やし、一文字ずつ子がなければ作って進み、各nodeの通過数も増やす。末尾nodeの終端数を増やす。prefix Pをたどったnodeの通過数がPで始まる登録文字列数、終端数がPそのものの個数である。辺がなければ0。空文字列の挿入はrootの両数へ寄与する。
辞書順列挙ではnodeの終端を先に出し、子を文字昇順にDFSする。prefix自身がその延長より先に来るためこの順になる。子の通過数を使えばk番目も、終端の重複分を引き、子の個数を小さい文字から差し引いて降りることで得られる。登録文字列の削除は存在する終端数を確認し、同じpathの通過数を減らす。
成立条件と計算量
総入力長Lなら節点数は高々L+1。固定文字種の配列遷移で挿入・検索は文字列長に比例するが、空間はO(Lσ)。疎な連想配列では探索費用も含める。重複文字列と「prefix自身が終端」の扱いを分ける。
問題一覧
- ABC287 E「Karuta」 公式問題
- ABC353 E「Yet Another Sigma Problem」 公式問題組合せ: 局所寄与へ分解して集計順を交換する
技能・出典
主題: Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。)。既習技能: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。主タグ: Trieによる共有接頭辞の索引 / 補助タグ: 寄与の数え上げと順序交換
- ABC437 E「Sort Arrays」 公式問題
- ABC377 G「Edit to Match」 公式問題
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP
技能・出典
主題: 値域集約による部分列DP(末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間monoid要約(要約する値・単位元・結合的な合成規則を定義し、prefix fold・Segment Tree・SWAGで答えを求められる。) / 候補数を界して全列挙・有限case分解する(制約・生成パラメータ・固定選択数・有限caseから候補総数を界し、漏れなく全候補を生成・評価できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。) / event順にactive集合を更新する(値・時刻・座標順にeventを並べ、同値eventの処理順とactive集合の増分更新を設計できる。) / 交換論から選択順を導く(局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。)。主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC268 G「Random Student ID」 公式問題
技能・出典
主題: 局所寄与へ分解して集計順を交換する(数える対象を要素・組・値・区間のいずれかで一意に固定し、各対象が含まれる回数または指示変数の期待値を先に求めて総和できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。)。主タグ: 寄与の数え上げと順序交換 / 補助タグ: 法上の四則演算・高速累乗・逆元、Trieによる共有接頭辞の索引
- ABC403 E「Forbidden Prefix」 公式問題主題: 単調進行による償却解析
技能・出典
主題: 単調進行による償却解析(要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。)。既習技能: Trieで共有接頭辞を索引化する(文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。)。主タグ: 単調進行による償却解析 / 補助タグ: Trieによる共有接頭辞の索引
前提・学習成果・出典
習得対象の目安: 水色(1200–1599)。共有prefixを木にし、通過数・辞書順・文字遷移をnode上で管理する。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 文字列アルゴリズム。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-trie-prefix
習得する技能
- 文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: なし。
このUnitを直接前提とする単元: Aho–Corasick。
文字ごとの遷移を配列やmapで持ち、複数文字列の共有接頭辞を木として索引化する。
このUnitでは扱わないもの
- failure linkやZ値で接頭辞と接尾辞の一致状態を更新する文字列照合。