問題概要
V,K,?からなる文字列 $S$ が与えられる。?はワイルドカードである。以下の条件を満たす $1$ 以上 $|S|$ 以下の整数 $k$ を全て求めよ。
- $S$ 中の
?をV,Kのどちらかに適切に置き換えたところ、 $S$ は周期 $k$ を持つ文字列であった。
- $k+1$ 以上 $|S|$ 以下の全ての整数 $i$ について $S$ の $i-k$ 文字目と $i$ 文字目とが一致するとき、文字列 $S$ は周期 $k$ を持つと言う。
例えば $S=$
V??VKであるとき、 $S$ をVKKVKと置き換えるとこの文字列は周期 $3,5$ を持つ。他の周期は作れないので求めるべき整数の集合は $\{3,5\}$ である。例えば $S=$
?VK?であるとき、 $S$ をKVKVと置き換えるとこの文字列は周期 $2,4$ を持つ。また、 $S$ をKVKKと置き換えるとこの文字列は周期 $3,4$ を持つ。他の周期は作れないので求めるべき整数の集合は $\{2,3,4\}$ である。
制約
・$1 \le |S| \le 5 \times 10^5$
知らないと解けない系。これ自力で思いつくのは無理だと思います。
やることは ワイルドカードを含むパターンマッチング - Qiita に書いてある。
モチベーションとしては以下の感じ。
$S$ と reversed $S$ とで上手いこと畳み込みをしたい。
$A_k = \displaystyle \sum_{i+j=k} S_i S_{|S|+1-j}$ みたいな式を作ると $A_{|S|+1-d}$ が $i-j=d$ なる $S_i S_j$ の総和となる。こんな感じの行為をすると「場所の差が $d$ である文字の比較」が全ての $d$ に対して $O(|S| \log |S|)$ で出来そう。但し今回はこの式そのままでは上手く行かない。
モチベーションとしては、以下の条件を満たす関数を設計して $A_k = \sum_{i+j=k} f(S_i,S_{|S|+1-j})$ を取りたい。
- $f(x,y) = 0$ ( $x$ と $y$ とがマッチする場合)
-
$f(x,y) > 0$ ( $x$ と $y$ とがマッチしない場合)
これが実現すれば、 $A_d > 0$ であることと 距離 $d$ のマッチしない文字組が存在することとが同値になる。
実は ? $=0$, V $=1$, K $=2$ と対応させると $f(x,y) = xy(x-y)^2$ としてやると所望の関数が出来上がる。天才か？？？
$f(x,y) = xy(x-y)^2 = x^3y - 2x^2y^2 + xy^3$ とバラすと、 $x,x^2,x^3,y,y,y^2,y^3$ を書き並べた列を畳み込むことで $A_k = \sum_{i+j=k}$ が取れる。
これで「距離 $d$ にマッチしない文字組が存在するか？」の配列が得られた。 $S$ が周期 $k$ を取らないことと、ある $k$ の整数倍の整数 $l$ について距離 $l$ にマッチしない文字組が存在することとは同値なので、 $O(|S| \log |S|)$ の調和級数ゲーをやれば判定が出来る。
