automaton上のDP・行列遷移
概要
有限状態automaton(オートマトン)は、読んだ接頭辞を有限個の状態へまとめ、一文字ごとの次状態を定めたものである。ここでは、構成済みのautomatonを使って文字列を数える。まず一文字ずつ進むDPを作り、最後に数える状態を決める。その後、同じ遷移を巨大回数繰り返す場合に行列累乗へつなぐ。
考え方
「11」を避ける二状態から始める
0と1からなる長さ の文字列で、連続する部分文字列11を含まないものを数える。既に違反した列を捨てておけば、次の文字を置けるかは末尾が1かだけで決まる。そこで安全な接頭辞を、状態 「空列または末尾0」と、状態 「末尾1」へ分ける。
| 現在の状態 | 0を追加 | 1を追加 |
|---|---|---|
11ができるので捨てる |
長さ の安全な接頭辞のうち、状態 にある個数をそれぞれ とする。長さ0では空列が一つなので初期値は 。表の遷移を、到着先ごとに足すと
となる。順に 、、 を得る。長さ2の列は00, 01, 10の3通り、長さ3は000, 001, 010, 100, 101の5通りである。
末尾が1でも、その時点では違反していない。従って答えは と、全ての安全状態を足す。状態 だけを足すと「末尾が0」という余計な条件が付く。長さ0も許す設定なら、答えは空列の1通りになる。
一文字の遷移と、最後に受理する状態
一般に、各状態と文字から次状態が一意に決まるautomatonを用意する。状態 に文字 を追加した次状態を とし、 を「長さ まで作り、途中で違反せずに状態 へ来た文字列の個数」とする。開始状態を とすると、初期値は 、他は0である。
各長さで次の配列を0に戻し、各状態と選べる文字について
と更新する。禁止pattern(連続する部分文字列として避けたい文字列)が完成する遷移は、加算せず捨てる。禁止情報には、同時に完成する短いpatternも含める。具体的な遷移表の構築は直接前提の有限状態automatonの構成で扱う。
この更新が正しいのは、長さ の列から末尾一文字を取り除くと、直前の接頭辞と追加文字が一意に定まるためである。同じ状態の接頭辞は、同じ文字を置けて同じ次状態へ進むので、個数をまとめて更新できる。異なる文字が同じ遷移先へ進む場合も、出来上がる文字列は別物なので、それぞれ加算する。
最後に答えへ含める状態を受理状態と呼ぶ。禁止patternの回避だけなら、違反する遷移を全て捨てた後に残る全状態が受理状態である。末尾などの追加条件があれば、それを満たす状態だけを選ぶ。開始状態から文字列を読む経路が一意に決まることも必要であり、非決定性automatonの複数経路をそのまま足すと、同じ文字列を重複して数え得る。
全patternの出現には既出集合を加える
今度は、空でない 個のpatternを全て含む列を数えたい。末尾の一致状態だけでは、過去に現れて末尾から消えたpatternを忘れてしまう。
Aho–Corasickでは、読んだ列の接尾辞のうち、いずれかのpatternの接頭辞でもある最長のものを状態として残す。例えば必要なpatternが0と10なら、pattern全体も接頭辞に含むため、10が完成したときの状態は10である。一方、長さ3の000と100はともに状態0で終わるが、後者だけが既に10を含む。100では、途中の10で両patternが現れた後、最後の0を追加すると状態が10から0へ移る。このように、末尾の一致状態が同じでも、それまでに出現したpatternの集合は異なり得る。
そこで状態を とする。 は元のautomatonの状態、 は既出集合を表すbitmaskで、bit が1ならpattern は既に出現している()。状態 で末尾に一致するpattern全てのmaskを とすると、一文字 の更新は
である。初期状態は 。10を読み終えるときは、10とその末尾の0が同時に現れるので、両方のbitを立てる。こうした出力情報をAho–Corasickなどで準備してから、DPへ渡す。
長さ まで進めた後、 の状態だけを、全ての について足す。全patternがまだ揃っていなくても、その接頭辞を途中で捨ててはいけない。後の文字で揃う可能性があるためである。逆に、一度全bitが立つfull maskになった後も長さ まで進める。途中で答えへ加えると、指定長より短い列も数えてしまう。
禁止は出現した瞬間に遷移を捨て、全出現の要求は履歴を残して最後に選ぶ。 どちらも受理条件から必要な状態を逆算する点は同じである。元のautomatonが 状態なら、maskを含む組合せは 状態となる。以下の状態数 は、このような追加情報まで含めた完全な状態の個数を指す。
固定遷移を行列へまとめる
一文字ずつのDPが間に合わないほど が大きくても、全ての位置で同じ遷移を使うなら反復をまとめられる。長さ の各状態の個数を並べた列ベクトルを とし、出発元 、到着先 に対する行列の要素を次の向きで定義する。
すなわち、行が到着先、列が出発元である。行列積の 成分は、各出発元の個数にそこからの文字の選び方を掛けて足したものなので、一文字のDPと一致する。
11回避で状態を の順に並べると、
となり、通常DPと同じ個数を得る。答えは の受理状態の成分和である。長さ0なら は単位行列なので、初期状態が受理されるかだけを調べればよい。
行列要素は「辺があるか」の0/1とは限らない。文字種をa,b,cとし、aaだけを禁止するなら、「空列または末尾がa以外」の状態へはbでもcでも戻る。この要素は2であり、1にすると文字列を数え落とす。行列作成時も、各文字について要素を1ずつ増やす。
必要なときは法上の四則演算・高速累乗・逆元の二分累乗と同様に、指数を二進数で処理する。 を順に作り、 の立っているbitに対応する行列をベクトルへ掛けると、長さを一つずつ進めずに済む。手順の一般形は固定線形遷移を巨大回数進めるで学べる。
成立条件と計算量
遷移表が構築済みで、一文字の遷移・maskのOR・個数の加算を定数時間で行えるとする。長さ ・完全な状態数 ・文字種数 なら、通常DPは 時間。長さの軸を現在と次の二配列へ分けると作業領域は となる。ここで に長さの軸は含めない。全pattern充足の が大きいと、 の分だけ通常DPでも重くなる。
行列を密に持つ場合、初期行列の構築は 時間、 の累乗は 時間・ の作業領域を使う。 なら初期ベクトルをそのまま使い、 なら行列とベクトルの積一回でよい。元のautomatonの遷移表を 状態・ 文字で保存するなら、別に の領域が必要であり、表そのものの構築時間は前提単元の方法で評価する。個数を固定の法で管理する場合の評価で、整数をそのまま大きくする場合は演算自体の費用も考える。
従って、長さを一つずつ進められるなら通常DPを使い、状態数が小さく、長さが巨大で、遷移が位置によらず固定なら行列累乗を検討する。元の一文字遷移が疎でも、二乗後の行列が疎とは限らない。maskを足した後の で密行列の費用を見積もる。位置ごとに選べる文字が違う場合や、上限との比較が位置の数字に依存する桁DPでは、同じ の累乗をそのまま使えない。
ABC305 Gは、短い禁止patternを判定できる末尾を状態に残し、最大 の長さを行列累乗で進める接続例である。ABC419 Fは、末尾の一致状態と既出maskを持ち、長さ100以下まで通常DPを進めてfull maskを集計する例である。patternが8個以下なのでmaskを持てる一方、密行列へ変えると組合せ状態数の三乗が重くなる。以下の公式根拠と本単元の小例を対応させ、状態数と反復回数の両方を見て手法を選ぶ。
到達可能性を求める場合は個数の加算をORへ、費用最小なら候補の集約をminへ変えるなど、同じ状態と合法遷移を再利用できる。ただし、行列にも集約と経路の連結に対応する演算が必要であり、数え上げ用の通常の和・積をそのまま使うわけではない。
問題一覧
この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
関連問題
他の主題と組み合わせる問題を読む
以下はこのUnitのOutcomeを追加で学ぶ技能または既習技能として参照する、別のUnitを主題とする問題です。
- ABC228 G「Digits on Grid」 公式問題
技能・出典
主題: 非決定性automatonのsubset construction(同時に存在し得るNFA状態集合を一つのDFA状態とし、文字ごとの集合遷移と受理条件を構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: automaton上のDP・行列遷移、非決定性automatonのsubset construction / 補助タグ: 部分集合・bitmask状態DP
- ABC301 F「Anti-DDoS」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 法上の四則演算・高速累乗・逆元(剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。) / 同値な状態を正規化する(対称操作で同値な状態の標準形と不変量を選べる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 法上の四則演算・高速累乗・逆元、状態・配置の正規化
- ABC305 G「Banned Substrings」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: 線形遷移・行列累乗
- ABC391 G「Many LCS」 公式問題主題: 最小十分状態からDPを設計する
技能・出典
主題: 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。既習技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。主タグ: DPの最小十分状態 / 補助タグ: automaton上のDP・行列遷移
- ABC418 G「Binary Operation」 公式問題主題: 有限状態automatonの構成
技能・出典
主題: 有限状態automatonの構成(未来の一文字遷移を決める有限同値類を定義し、pattern suffix・subsequence進行・圧縮DP rowなどから完全遷移表を構成してDPや行列累乗に接続できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 区間合成・領域分割DP(区間や長方形の分割点を列挙し、独立な小領域の答えを合成して領域サイズ順に計算できる。) / 最小十分状態からDPを設計する(採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。)。主タグ: automaton上のDP・行列遷移、有限状態automatonの構成 / 補助タグ: DPの最小十分状態、区間合成・領域分割DP
- ABC419 F「All Included」 公式問題主題: Aho–Corasick
技能・出典
主題: Aho–Corasick(複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 部分集合・bitmask状態DP(bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。)。主タグ: Aho–Corasick、automaton上のDP・行列遷移 / 補助タグ: 部分集合・bitmask状態DP
- ABC458 F「Critical Misread」 公式問題主題: Aho–Corasick
技能・出典
主題: Aho–Corasick(複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。)。追加で学ぶ技能: automaton上のDP・行列遷移(位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 固定線形遷移を巨大回数進める(固定線形遷移を行列または漸化式にし、巨大回数後の値を求められる。)。主タグ: Aho–Corasick、automaton上のDP・行列遷移 / 補助タグ: 線形遷移・行列累乗
前提・学習成果・出典
習得対象の目安: 青色(1600–1999)。構成済みautomatonと位置の直積を使い、禁止状態と受理状態を区別して数える。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 接頭辞から更新する有限状態DP。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-automaton-dp
automaton上のDP・行列遷移
習得する技能
- 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 最小十分状態からDPを設計する、有限状態automatonの構成(後の章)。
このUnitを直接前提とする単元: なし。
有限pattern automatonの完全遷移を構成できるようになった後、位置・長さとの直積状態で受理列を数え、桁上限がある場合だけ桁DPと組み合わせる。
このUnitでは扱わないもの
- automaton上のDP・行列遷移の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。
根拠
今回の接続の確認日: 2026-10-26。11回避などの小例は本単元の説明用に作ったもので、公式解説からの引用ではない。