メモ帳

ABC272 F - Two Strings 筋肉解法

パワー

問題概要

問題リンク：

要約：

長さ $N$ の文字列 $S,T$ が与えられる
$X$ を $i$ 回 rotate した文字列を $f(X,i)$ と書く
組 $(i,j)\ (0 \le i,j \le N-1)$ であって、 $f(S,i) \le f(T,j)$ (辞書順序) を満たすものの個数を求めよ

解法

想定解法は Suffix Array ですが、ローリングハッシュのみでも解けます。

流れとしては、

$f(T,0),f(T,1),\dots,f(T,N-1)$ を辞書順で昇順ソート
$i=0,1,\dots,N-1$ に対し、 $f(S,i) \le f(T,j)$ を満たす最小の $j$ を二分探索で求め(存在しないなら $j=N$ )、解に $N-j$ を加える

となります。

もちろん $f(T,0),f(T,1),\dots,f(T,N-1)$ を実際に作ってしまうとそれだけで MLE になります。

これは $T$ を長さ 2 倍にしたもののハッシュの累積和を取っておき、その左端の index を $f(T,j)$ と見なせばよいです（実装参照）。

ローリングハッシュを用いた文字列の辞書順比較

ローリングハッシュと二分探索を組み合わせると、2つの文字列があったときに、それらの部分文字列の common prefix の最長を高速に求めることができます。
これにより、2 つの文字列の部分文字列の比較が高速に行えます。

さらにこれを比較関数とすることで、部分文字列のソートを $\log$ 2個で行えます。

（↓同様の手法で解くことができる問題。というよりこれの tester 解を見てこの記事を書いています）

同様に、 $i=0,1,\dots,N-1$ に対して $f(S,i) \le f(T,j)$ を満たす最小の $j$ を求めるパートも $\log$ 2個で行えます。

実装

ローリングハッシュはライブラリにしておくといざという時に役立ちます。

提出：
atcoder.jp

なんか 2000ms って書いてますね。見なかったことにしてください

定数倍高速化すればもう少しマシにはなると思います。
(ちなみに mod1000000007 でやったら衝突しました。それはそう)

まとめ

定数倍高速化を入れて君だけの最強ローリングハッシュを作ろう！