ABC 307 Ex — Marquee

考察

一周期U=S+'.'^(W−1)を作り、その先頭W−1文字を再度付けたTの各length-W windowが、L+W−1個のdisplay statesと一対一対応する。

英字と.を相異なる小さい整数に変換し、畳み込み用のP配列では_の値を0、それ以外を文字符号とし、maskはm_k=[P_k≠_]とする。各配置の不一致スコアΣ(T−P)^2maskは非負で、指定位置がすべて一致するときだけ0になる。

棄却する候補: 各stateのW positionsをPと直接比較する。

(L+W)Wが最大Θ(W^2)となる。

採用する候補: mismatch polynomialをΣT^2mask−2ΣTP+ΣP^2へ展開し、reverseしたP側arraysとのNTT convolutionsで全alignmentsを求める。

各cross-correlationを一回のconvolutionで一括評価でき、score 0のwindowsだけを数えられる。

Tにはwildcardがないため(P指定位置だけの)squared differenceで十分で、character valuesを0…53にすればscoreは998244353未満になりmodulo zeroの偽一致が起きない。

cross-correlationはpattern arraysをreverseしてconvolutionし、window start iに対応するcoefficientを正しいoffsetから読む。

典型の発動条件

wildcard matchingのmismatch polynomial

発動条件: 有限alphabetの全alignmentsで、wildcard以外の不一致数を一括判定したいとき。

指定位置だけ(x−y)^2を足し、sum zeroをmatch条件にする。

畳み込みによるcross-correlation

発動条件: 全shiftについてΣ_k F(T_{i+k})G(P_k)型の量が必要なとき。

pattern coefficient列をreverseしてNTTし、各window scoreのcross termsを得る。

問題固有の要素

periodic displayをcycleごと複製せず、一周期とW−1文字のprefixだけで全length-W windowsを線形文字列に埋め込める。

別の問題へ持ち帰る視点: cyclic window列挙はperiod列へwindow length−1のprefixをappendする。

正当性

周期U=S+空白W−1個を延長すれば全display状態が各長さWwindowに一度現れる。指定位置の二乗差和は非負で0と完全一致が同値。文字符号の範囲とWにより総scoreは法未満なのでmod0の偽一致がない。二乗展開の相関を反転patternとの畳み込みで評価し、正しいwindow範囲だけ数える。

実装上の注意

  • .も英字と異なる値を割り当て、_だけ値とmaskをともに0にする。
  • convolution coefficient indexとvalid start range0…L+W−2を合わせ、余分なwindowsを数えない。

復習の核

  • 全shift matchingは不一致時だけ正になるcharacter pair scoreを代数展開できないか考える。
  • modular convolutionでzero判定するなら、真のscore上界をmodulus未満にしてcollisionを排除する。

計算量と制約

時間

O((L+W)log(L+W))。固定本数のNTT相関を計算する。

空間

O(L+W)。

制約との対応

公式制約の確認範囲: Time limit: 5 sec; Memory limit: 1024 MiB; Constraints: 1 \leq L \leq W \leq 3\times 10^5; L and W are integers.; S is a string of length L consisting of uppercase and lowercase English letters.; P is a string of length W consisting of uppercase and lowercase English letters, ., and _.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: NTT・FFTで畳み込みと相互相関を求める

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 畳み込み・相互相関

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

      学習の位置

      体系上の位置: NTT・FFTで畳み込みと相互相関を求める

      • 係数積和または反転列との相互相関を多項式積へ変換し、NTT・FFTで必要な係数範囲を計算できる。

      この解説で扱わないこと:

      • 組合せ解釈を必要とする生成関数の設計、および逆数・対数・指数などのFPS演算。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題