Trieによる共有接頭辞の索引
文字列集合の各文字遷移を木として共有し、prefix通過数・prefix DP・辞書順探索をnode上で処理する。
この典型を扱う単元: Trieで共有接頭辞を索引化する
検索別名: Trie、prefix tree、トライ木
未知問からこの典型を見つける手掛かり
- 扱う対象
- node
- 接頭辞
- 文字
- 文字列集合
- 使う手掛かり
- 一文字ずつ挿入
- 共通prefix
- 辞書を構築
- 保つ不変量
- prefix node
- 子への文字遷移
- 通過数
- 求めるもの
- prefix query
- 共通接頭辞
- 文字列変換
- 辞書順
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 文字列状態表現
関連する典型
学習成果と学習単位
文字列集合をTrieへ挿入し、nodeの通過数・子遷移・辞書順を使って共有接頭辞の問いを処理できる。
Trieで共有接頭辞を索引化するで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC287 E「Karuta」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
- ABC353 E「Yet Another Sigma Problem」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
- ABC437 E「Sort Arrays」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC240 Ex「Sequence of Substrings」 公式問題主題: 値域集約による部分列DP / 補助タグ
技能・出典
主題: 値域集約による部分列DP
主タグ: 値域集約による部分列DP / 補助タグ: 有界全列挙・有限case分解、event・値順のオフライン走査、貪欲法と交換論、区間monoid要約、Trieによる共有接頭辞の索引
- ABC268 G「Random Student ID」 公式問題主題: 局所寄与へ分解して集計順を交換する / 補助タグ
- ABC287 E「Karuta」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
- ABC353 E「Yet Another Sigma Problem」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
- ABC377 G「Edit to Match」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ
- ABC403 E「Forbidden Prefix」 公式問題主題: 単調進行による償却解析 / 補助タグ
- ABC437 E「Sort Arrays」 公式問題主題: Trieで共有接頭辞を索引化する / 主タグ