考察
一周期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 _.
出典