有限状態automatonの構成
文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。
この典型を扱う単元: 有限状態automatonの構成
検索別名: DFA、finite-state automaton、有限オートマトン
未知問からこの典型を見つける手掛かり
- 扱う対象
- 受理・集計状態
- 接尾辞または圧縮DP row
- 有限状態
- 使う手掛かり
- 一文字更新が有限種類
- 未来等価
- 禁止pattern
- 要求subsequence
- 保つ不変量
- 受理条件
- 完全遷移
- 有限状態
- 求めるもの
- automaton構築
- 文字列状態圧縮
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: 文字列状態表現
関連する典型
学習成果と学習単位
未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。
有限状態automatonの構成で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC264 G「String Fair」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC305 G「Banned Substrings」 公式問題主題: 有限状態automatonの構成 / 主タグ
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成 / 主タグ