長さ $L$ ( $L \le 10^5$ ) の A,G,T,C からなる文字列 $S$ が与えられる。
この文字列のうち連続する $2k$ 文字の連続部分列であって、同じ長さ $k$ の文字列が $2$ 度繰り返されているものの数を数えよ。
(文字種の制限は使わないので、任意の英大小文字からなる文字列だとしても別に良い)
繰り返しのひとつあたりの長さ $k$ を固定して、 $O(L/k)$ 程度で解くことを考える。こうすると調和級数の $\log$ 1つを増やせば元の問題を解ける。
結論から言ってしまうと、次の手順で解ける。
- 文字列の $1$ 回目と $2$ 回目との仕切りの位置を固定し、これを文字列の左端から右端へと動かすことを考える。 CATTCGATTCGAT は、仕切りが $6$ 文字目の直後に入っているイメージ。
- もし、今注目している場所の両側で文字列が一致しているなら、その部分はまともと認定して仕切りを $k$ 文字右に進める。
- そうでないなら、不一致となる文字の組のうち最も右にあるものを検出し、そのうち片側を追い出すように仕切りを右に進める。(両側が残っている限りふたつの文字列は揃わないことに注意)
図中青の仕切りを緑の位置に動かすような感じ。
文字列が不一致となる位置の検出は、ロリハで $\log$ を1つ増やせばできる。
これが $O(L/k)$ 回で済む証明は次の通り。
- 文字列が一致しているパターンは、仕切りが一度に $k$ 文字右に進むので明らか。
- 文字列が一致しないパターンで例えば右から $t$ 文字は一致していたとする。このとき仕切りは $k-t$ 文字右に進む。その次の仕切りの操作を考えた時、その時点での文字列のうち左から $t$ 文字は揃っていることが保証されるため、少なくとも仕切りは $t$ 個以上右に進む。なので、結果として $2$ 手で $k$ 文字以上仕切りが右に進む。
より詳細には、文字列が一致しているパターンの直後は連続して文字列が一致している部分が存在しているパターンがある (AGCAGCAGCT のような場合) ので、その数を数えなければならない。文字列が一致しているパターンの連続の場合は定数時間、一致しているパターンの直後に一致していないパターンを引いた場合は最も左の不一致の検出の $\log$ 1つでできる。これ以上の詳細は実装参照。
結果、全体で $\log$ 2つでこの問題に正解できる。
「一見厳しそうだが実は間に合う」という、計算量解析が美しい問題。
想定解は $\log$ 1つっぽい見た目をしているが、読解できなかった…
