以下、記法は公式解説と同様です。

長さ \(M\) の乱数列 \(R\) をとり、長さ \(N - M + 1\) の数列 \(f, g\) を

\[ f_i = \sum_{j=1}^M \mathbf{1}(A_{i + j - 1} > 0) B_j R_j, \]

\[ g_i = \sum_{j=1}^M A_{i + j - 1} \mathbf{1}(B_j > 0) R_j \]

で定めると、 \(i\) が条件を満たすとき、 \(R\) の取り方によらず \(f_i / g_i\) の値が一定となるか \(f_i = g_i = 0\) となります。したがって何度か \(R\) を取り直して \(f\) や \(g\) を計算し、\(f_i / g_i\) の値が不変となる \(i\) の個数を求めれば良いです。こちらの解法も計算量のボトルネックは \(f\) や \(g\) の計算のための FFT (NTT) を用いた畳み込みで、想定計算量は \(O(N \log N)\) です。