ABC477 C - Range Search Query
範囲検索クエリ
考え方
まず、愚直にやるのは簡単。
ただし、それでは計算量が $O(QN|T|)$ となりTLEする。
そこで、メモ化を行う。
つまり、事前に $T$ の文字列がある位置の先頭を全て愚直な全探索で拾っておく。
すると、$L$ 以上 $R-|T|+1$ 以下の数がこの中にあるかどうかという問題になる。
これは、該当位置を $1$、そうでない位置を $0$ とする数列の累積和を利用することで、毎回 $O(1)$ で求まる。
よって、全体の計算量 $O(N|T|+Q)$ で解ける。
入力例1での動作
入力を受け取る。
q: 3
s: "abcdabc"
t: "bc"$S$ の中で $T$ が始まる位置を調べる。
$|T|=2$ なので、スタート位置として調べるのは $1$ 文字目から $6$ 文字目までである。
各スタート位置から $2$ 文字を取り出し、$T$ と一致するかを確認する。
一致するなら $1$、そうでなければ $0$ とする。
| スタート位置 | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|
| $S$ の部分文字列 | "ab" |
"bc" |
"cd" |
"da" |
"ab" |
"bc" |
| $T$ と一致するか | いいえ | はい | いいえ | いいえ | いいえ | はい |
| 値 | $0$ | $1$ | $0$ | $0$ | $0$ | $1$ |
したがって、$T$ が始まる位置に対応する列は $0,1,0,0,0,1$ となる。
この列の先頭に $0$ を $1$ つ置き、左から累積和を取る。
先頭から $k$ 個の合計は、次のようになる。
| $k$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
|---|---|---|---|---|---|---|---|
| $k$ 文字目の値 | - | $0$ | $1$ | $0$ | $0$ | $0$ | $1$ |
| 先頭 $k$ 個の累積和 | $0$ | $0$ | $1$ | $1$ | $1$ | $1$ | $2$ |
例えば、スタート位置 $2$ 以上 $5$ 以下にある $1$ の個数を考える。
先頭 $5$ 個の累積和から、先頭 $1$ 個の累積和を引けばよい。
この場合は $1-0=1$ となり、範囲内に $T$ のスタート位置があるとわかる。
各クエリについて、$T$ のスタート位置として使える範囲を確認する。
| クエリ | スタート位置の範囲 | 累積和の差 | 答え |
|---|---|---|---|
| $[2,6]$ | $[2,5]$ | $1-0=1$ | Yes |
| $[3,5]$ | $[3,4]$ | $1-1=0$ | No |
| $[3,7]$ | $[3,6]$ | $2-1=1$ | Yes |
したがって、出力は順に Yes, No, Yes となる。
注意点
添字範囲がかなり複雑になる。
$T$ のスタート位置として採用可能なのは、$N$ 番目までではなく、$N-|T|+1$ 番目の文字までである。
このこと自体がややこしい上に、$N-|T|$ ではなく $+1$ が必要なのがさらにややこしい。
しかも、$T$ が $S$ より長い可能性すら、制約では否定されていない。
加えて、クエリで来る $L$ や $R$ が、どうみても $L$ の後ろや $R$ の前に $|T|$ 文字ない場合もある。
これらを全て例外処理しなければならないので、かなり大変。
別解
本来はD問題レベルなのだが、二分探索を使った方が、気を使うところが少なくて簡単。
スタート範囲は気をつけなければいけないが、それ以外は全て注意点を無視できる。
しかも累積和を取らなくてもよいのもうれしい。
「別解」のコード参照。