ABC 458 F — Critical Misread

考察

禁止文字列をまだ含まないprefixの将来は、禁止patternのprefixでもある最長suffixだけで決まる。この状態集合はAho-Corasick trieのnodeに一致する。

採用する候補: 禁止patternからAho-Corasick automatonを作り、禁止出力stateを除いた文字遷移数行列 M を構築して、初期vectorに M^N を掛ける。

automaton stateがpattern出現判定に必要十分なsuffix情報を保持し、長さ一文字のDP遷移は時刻に依存しないため巨大Nを行列二分累乗できる。

棄却する候補: 末尾最大K文字をそのままstateにしたDPをN段行う。

state数が26^K、段数がN≤10^9で両方とも制約を超える。

failure linkにより現在suffixに文字cを足した後の最長pattern prefix suffixへ定数時間遷移できる。

同じstate pairへ移る文字種類数を行列要素として足し、pattern terminalまたはそのfailure祖先terminalのstateへの遷移を除外する。

全patternをtrieへ入れfailure linkとcomplete gotoをBFS構築し、terminal伝播する。safe node間で26文字の遷移をcountしたmatrixを作り、root one-hot vectorをbinary exponentiationでN回遷移させ、safe state成分を総和する。

典型の発動条件

Aho-Corasick automaton DP

発動条件: 複数禁止patternを含まない文字列数を数えたいとき。

最長prefix-suffix状態とfailure linkで全patternを同時監視する。

遷移行列の二分累乗

発動条件: 有限automaton上の固定遷移を巨大長だけ繰り返すとき。

文字種類数を重みとするstate遷移行列を累乗する。

問題固有の要素

末尾文字列DPは、将来patternを完成させる可能性が同じsuffixをautomaton stateとして最小化できる。

別の問題へ持ち帰る視点: 長さが巨大なautomaton DPは、遷移が時間一様なら線形漸化式の行列累乗へ移す。

正当性

AC状態は将来の禁止検出に必要なsuffixを完全に保存する。failure祖先terminalも伝播したunsafe stateへの遷移を落とせば、safe graphのpathと禁止を含まない列が全単射。matrix要素は同state間の文字数を表すので積は文字選択の全方法を数え、N乗のroot分布成分和がsafe長N列数になる。

実装上の注意

  • failure先terminalを含むnodeも禁止stateとして伝播し、そこへの遷移を数えない。行列の行列vector向きとN=0基底を統一する。

復習の核

  • pattern prefix集合とfailure遷移を小例で構築し、terminal伝播後のsafe遷移行列が一文字DPを正確に表すか確認する。

計算量と制約

時間

O(S³ log N+26S)、S≤1+Σ|S_i|≤101。AC安全state行列のN乗。

空間

O(S²+Σ|S_i|)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: N is an integer between 1 and 10^9, inclusive.; K is an integer between 1 and 10, inclusive.; S_i is a string consisting of lowercase English letters with length between 1 and 10, inclusive.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Critical Misread の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Aho–Corasick

主題
  • Aho–Corasick: 複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。
追加で学ぶ技能
  • automaton上のDP・行列遷移: 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
既習技能

主タグ: Aho–Corasick automaton上のDP・行列遷移

補助タグ: 線形遷移・行列累乗

執筆: abc-explanation-author1.1.1 / revision 1

学習の位置

体系上の位置: Aho–Corasick

  • 複数patternのTrieへfailure linkと出力情報を加え、Aho–Corasick automaton上で一致状態を更新できる。
  • 位置・長さとautomaton stateの積状態を作り、禁止条件を満たす遷移を除き、処理終了時に目的言語の受理状態を集計する。禁止パターン回避では検出状態を除外し、全パターン充足では出現maskが全て立つ状態を受理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

先に読む単元:

  • 有限状態automatonの構成 — 文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
  • 固定線形遷移を巨大回数進める — 一回分の状態遷移を表せることを前提に、固定線形変換を累乗して巨大回数後へ進める。
  • Trieで共有接頭辞を索引化する — 文字ごとの遷移を配列やmapで持ち、複数文字列の共有接頭辞を木として索引化する。

学習記録

状況更新: 更新記録なし

復習設定更新: 更新記録なし

端末内の保存状態を確認しています。

要復習一覧 / 学習記録のバックアップ / 解説に戻る

同じ単元の問題