ABC 419 F — All Included

考察

文字列を左から生成すると、将来pattern出現に影響する過去情報は「末尾のうちいずれかのS_iのprefixでもある最長suffix」と既出pattern集合だけである。

全pattern長合計は高々80なので、Aho-Corasick automatonでこのsuffix状態と一文字遷移、遷移時に新たに含まれるpattern maskを小さく持てる。

採用する候補: Aho-Corasick状態×既出pattern bitmaskの長さDP

26文字を追加してautomaton遷移し、destinationのoutput maskをORする。dpをL回進めたfull maskの総数が答えで、O(L·states·2^N·26)。

棄却する候補: 26^L個の文字列を生成して各S_iをsubstring検索する

候補数が指数的で、pattern matchingに必要なsuffix情報をautomaton stateへ共有できていない。

failure link先のoutput maskもnodeへ伝播すれば、ある文字追加で終端するpatternだけでなく、そのsuffixとして同時に出現する短いpatternも一度のORで記録できる。

未登録文字の遷移もfailure linkに従うcomplete DFAへ前計算すれば、DP内の一文字遷移をO(1)にできる。

S_iをtrieへ挿入して終端nodeにbit iを立て、BFSでfailure link・全26遷移・累積output maskを構築する。dp[start][0]=1からL文字、各state/mask/charでnextStateへ進みmask|output[nextState]へ加算し、最後にmask=(1<<N)-1を全stateで足す。

典型の発動条件

Aho-Corasick automaton

発動条件: 複数patternのsubstring出現を文字列生成DPの有限suffix状態にしたいとき。

trieとfailure linkでprefix/suffix一致をDFA遷移として前計算する。

bitmask DP

発動条件: 必要pattern数N≤8で、どれが既出かを追うとき。

automaton output集合をmaskへORして全包含状態を数える。

文字列生成DP

発動条件: 固定長のalphabet列を左から作り、有限automatonで性質を判定するとき。

位置・automaton state・付加maskを状態に26遷移する。

問題固有の要素

substring条件を各patternごとのKMP状態で別々に持たず、共有prefix trieとfailure suffixで合成した一automatonにまとめる。

別の問題へ持ち帰る視点: 複数substring制約の生成数え上げでは、AC state+達成maskが標準的な十分統計量になる。

正当性

Aho–Corasick状態は将来の一致へ必要な最長pattern-prefix suffixを保存する。failure出力をORすれば同時に終わる短patternも記録できる。既出maskは過去出現を忘れず、文字を一つ選ぶ遷移で各生成列を一意に構成する。exact L回後full maskだけ合計するので全patternを含む長さL列を過不足なく数える。

実装上の注意

  • failure link構築時にoutput maskを親failからORし、rootの欠損遷移をrootへ張る。DPはexact length L、加算はmod 998244353、rolling arrayでmemoryを抑える。

復習の核

  • patternが他patternのsubstring、共通prefix、重なって同時出現、Lが最長pattern未満の例を小alphabet全列挙と比較する。

計算量と制約

時間

O(26L·S·2^N)、S≤1+Σ|S_i|≤81。

空間

O(S2^N+26S)。長さ軸rolling。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq N\leq 8; 1\leq L\leq 100; N and L are integers.; Each S_i is a string of length 1 and 10, inclusive, consisting of lowercase English letters.; S_i\neq S_j\ (i\neq j)

出典

分類・前提・執筆情報

掲載状態: 収録済み

All Included の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: Aho–Corasick

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

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

補助タグ: 部分集合・bitmask状態DP

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

学習の位置

体系上の位置: Aho–Corasick

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

先に読む単元:

  • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。
  • 有限状態automatonの構成 — 文字を一つ加えた後の未来の挙動が等しい履歴を有限状態へ同値化し、pattern suffix・部分列進行・圧縮DP rowなどから全文字の完全遷移表を構築する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
  • Trieで共有接頭辞を索引化する — 文字ごとの遷移を配列やmapで持ち、複数文字列の共有接頭辞を木として索引化する。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題