典型タグ

Trieによる共有接頭辞の索引

文字列集合の各文字遷移を木として共有し、prefix通過数・prefix DP・辞書順探索をnode上で処理する。

この典型を扱う単元: Trieで共有接頭辞を索引化する

検索別名: Trie、prefix tree、トライ木

未知問からこの典型を見つける手掛かり

扱う対象
  • node
  • 接頭辞
  • 文字
  • 文字列集合
使う手掛かり
  • 一文字ずつ挿入
  • 共通prefix
  • 辞書を構築
保つ不変量
  • prefix node
  • 子への文字遷移
  • 通過数
求めるもの
  • prefix query
  • 共通接頭辞
  • 文字列変換
  • 辞書順
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: 文字列状態表現

    関連する典型

      学習成果と学習単位

      代表問題

      この典型の考え方を具体的な問題で確かめるための入口です。

      関連問題

      この典型が主タグまたは補助タグとして付いている問題です。