長さの等しい \(2\) つの文字列 \(X,Y\) が、少なくとも一方が _ である箇所を除いて一致しているとき「マッチする」と表現することにします。また、\(2\) つの文字についても同様の表現を用います。

電光掲示板のありえる状態を適切につなぎ合わせた長さ \(N+2W-2\) の文字列を \(T\) とします。例えば 入力例 \(1\) に対しては \(T=\) ABC....ABC. となります。このとき問題は「\(T\) の長さ \(W\) の部分文字列うち\(P\) とマッチするものは何個あるか？」となります。

\(P\) がワイルドカード _ を含まなければKMP法などにより解けますが、_ を含む今回の問題ではこの方針で解くことは困難です。

そこで ABC196F のような方針を考えます。ABC196Fの本質は「\(0\) または \(1\) である \(2\) つの文字 \(x,y\) について、\(x=y\) のとき \(1\) 、\(x\neq y\) のとき \(0\) となる関数 \(f(x,y):=xy+(1-x)(1-y)\) を考え、全ての \(i\) に対しての \(\sum_k f(T_{i+k},P_{k})\) を畳み込み積を用いて求める」でした。今回も同様のアプローチが有効です。

文字 \(x,y\) がマッチするとき \(0\)、マッチしないとき正の値を返すような関数 \(f(x,y)\) を考えます。すなわち

• \(x,y\) の少なくとも一方が _ であるとき \(f(x,y)=0\)
• \(x=y\) であるとき、\(f(x,y)=0\)
• どちらでもないとき、\(f(x,y)>0\)

を満たす関数 \(f(x,y)\) を取ります。このとき、\(2\) つの文字列 \(X,Y\) がマッチする必要十分条件は \(\sum_k f(X_k,Y_k)=0\) であることです。

「全ての \(i\) に対しての \(\sum_k f(T_{i+k},P_k)\)」を高速に求めることができるような \(f\) を考えます。

ワイルドカード _ に \(0\) を、ワイルドカード以外の各文字に \(0\) でない相異なる値を割り当て、(文字と割り当てられた数を同一視すると、) \(f(x,y)=(x-y)^2xy\) は上で述べた性質を満たします。
このとき、 \(\sum_k f(T_{i+k},P_k)=\sum_k(T_{i+k}^3P_i-2T_{i+k}^2P_i^2+T_{i+k}P_i^3)\) であることから、適切な数列の畳み込み積を考えることで、全ての \(i\) についての \(\sum_k f(T_{i+k},P_k)\) を \(O((N+W)\log(N+W))\) で求めることができます。

よってこの問題は \(O((N+W)\log(N+W))\) で解けました。

細かな注意

FFTを行うにあたって \(998244353\) など \(\bmod M\) で計算を行うと、\(\sum_k f(T_{i+k},P_k)\) が\(M\) の倍数となるケースで誤判定する可能性があります。文字への値の割り当てを十分ランダムにした場合、マッチの誤判定確率は expected \(O(1/M)\) 、1ケースあたりの不正解確率はexpected \(O((N+W)/M)\) となるため、AC とならない確率は無視できない程度となります。

この方針で十分高い確率で AC を得るためには、mod や、文字への値の割り当てを複数回試す必要があります。

今回は \(T\) がワイルドカードを含まないことから、\(f_k(x,y)\) として \((x-y)^2[y\neq \)_\(]\) を取ることができます( \([\mathrm{Prop}]\) は \(\mathrm{Prop}\) が真のとき \(1\) 、偽のとき \(0\) )。さらに文字に割り当てる値の範囲を \(0\) から \(53\) とすることで、\(\sum_k f(T_{i+k},P_k)<998244353\) になり、この場合には \(\bmod 998244353\) で全ての計算を行っても必ず正しい答えを得ることができます。

writer解(C++)
writer解(Python)

別解

乱数列 \((R_i)\) を任意にとり、\(Z_k\) を、\(P_k=\) _ ならば \(0\)、\(P_k\neq \) _ ならば \(R_k\) と定めます。また、文字から値への写像を任意に \(1\) つ固定し \(c\) とします。文字列 \(T\) の \(i\) 文字目からの部分文字列と \(P\) がマッチする必要条件は、\(\sum_k c(T_{i+k})Z_k=\sum_k c(P_k)Z_k\) が成り立つことです。左辺は畳み込みにより、全ての \(i\) についてを \(O((N+W)\log(N+W))\) で求めることができます。右辺は \(i\) に依存しない定数であり、愚直に \(O(W)\) で求められます。

この等式の成立を \(\bmod M\) で判定するとき、誤判定確率 は expected \(O(1/M)\) であり、前述の解法同様、\((R_i)\) を複数種類試すことで、十分高い確率で AC を得ることができます。

この解法は en_translator さんによるものです。