D - Pre-Palindrome 解説
by 
iastm
高速化について
Rolling hash を使った高速化を解説します。Rolling hash に関する資料は以下があります。
参考資料
- Rolling hash について
- Rolling hash を使ってできる操作
以下を定義しておきます。
- 文字列 \(s\) の長さを \(|s|\) と表す
- 文字列 \(s\) の \(i\) 文字目を \(s_i\) と表す
- 文字列 \(s\) の部分文字列 \(s_\ell s_{\ell+1}\dots s_r\) を \(s[\ell:r]\) と表す
- 文字列 \(s\) を反転して得られる文字列を \(\text{rev}(s)\) と表す
- 文字列 \(s\) の非空部分文字列であって、良い文字列であるものを \(s\) の良い部分文字列と呼ぶ
Manacher’s algorithm と同様に、\(S\) の両端と文字の間に番兵文字|を挿入して得られる文字列 \(T\) を考えます。例えば \(S=\)ababaの場合、\(T=\)|a|b|a|b|a|です。\(S\) の各良い部分文字列 \(s\) は、\(T\) の次の \(2\) 通りの部分文字列に対応します。
- \(s_1\)
|\(s_2\)|\(\dots\)|\(s_{|s|}\) |\(s_1\)|\(s_2\)|\(\dots\)|\(s_{|s|}\)|
したがって、\(s\) に対応する良い部分文字列は \(T\) において \(2\) 回ずつ数えられるため、総数から重複を引けば答えが求まります。空文字列は|にも対応することに注意してください。また、\(T\) の良い部分文字列は全て奇数長であるため、場合分けを省略することができます。
\(T\) に対し、次のアルゴリズムが考えられます。
- 良い部分文字列の総数を表す変数 \(\mathtt{ans}\gets0\) を初期化する。
- 各 \(i\in\lbrace1, 2, \dots, |T|\rbrace\) について、\(i\) を中心とする良い部分文字列を以下の手順で数える。
- \(T[i+1:i+k_1]=\text{rev}(T[i-k_1:i-1])\) を満たす最大半径 \(k_1\) を二分探索で求める。\(\mathtt{ans}\) に \(k_1+1\) を加算する。
- ここで半径 \(k_1\) 以下の部分文字列は全て回文である。
- \(\ell=i-k_1-1\)、\(r=i+k_1+1\) とする。\(1\leq\ell\) かつ \(r\leq|T|\) なら、\(T[r+1:r+k_2]=\text{rev}(T[\ell-k_2:\ell-1])\) を満たす最大の整数 \(k_2\) を二分探索で求め、\(\mathtt{ans}\) に \(k_2+1\) を加算する。
- ここで半径 \(k_1+k_2+1\) 以下の部分文字列は、 \(1\) 文字を書き換えることで回文にすることができる。
- \(T[i+1:i+k_1]=\text{rev}(T[i-k_1:i-1])\) を満たす最大半径 \(k_1\) を二分探索で求める。\(\mathtt{ans}\) に \(k_1+1\) を加算する。
- \(\mathtt{ans}\) を出力する。
文字列 \(s, t\) に対し \(s=\text{rev}(t)\) の判定は rolling hash を使えば効率的にできます。Rolling hash に関しては以下のような前計算が必要です。
- 素数 \(P\) と正整数 \(K\) を選び、\(P\) 未満のランダムな非負整数 \(b_1, \dots, b_K\) を一様かつ独立に選ぶ。
- \(T\) と \(\text{rev}(T)\) を連結して得られる文字列を \(X\) とする。
- \(k\in\lbrace1, 2, \dots, K\rbrace\) について、以下を行う。
- \(h_{k, 0}=0\)、\(p_{k, 0}=1\) とする。
- 各 \(i\in\lbrace1, 2, \dots, |X|\rbrace\) について、\(h_{k, i}=(h_{k, i-1}\cdot b_k+X_i)\text{ mod }P\)、\(p_{k, i}=p_{k, i-1}\cdot b_k\text{ mod }P\) を求める。ここで \(X_i\) は文字を適当な整数に置き換えたものとする。
- \(X\) の部分文字列 \(s=X[\ell:r]\) のハッシュを \((H_{s, 1}, \dots, H_{s, K})\) として定義する。ただし、\(H_{s, k}=(h_{k, r}-h_{k, \ell-1}\cdot p_{k, r-\ell+1})\text{ mod }P\) とする。
- \(X\) の部分文字列 \(s, t\) のハッシュが一致するなら \(s=t\) とみなし、そうでないなら \(s\neq t\) と判定する。
以上より、全体の計算量は \(O(|S|K\log |S|)\) です。
ハッシュ衝突の確率を評価します。長さ \(|T|\) 以下の異なる文字列 \(s, t\) が衝突を起こす場合、各 \(k\in\lbrace1, \dots, K\rbrace\) について \((H_{s, k}-H_{t, k})\text{ mod }P=0\) を満たす必要があります。ここで \(H_{s, k}-H_{t, k}\) は \(b_k\) に関する \(|T|-1\) 次以下の非零多項式であり、その解は \(|T|-1\) 個以下であるため、一様かつ独立に選ばれたランダム整数 \(b_1, \dots, b_K\) が全て解である確率は \(\left(\frac{|T|-1}{P}\right)^K\) 以下です。
さらに、二分探索の途中で比較されるハッシュのペアは \(2|T|\lceil\log_2|T|\rceil\) 通り以下であるため、union bound より、アルゴリズム全体でハッシュ衝突が起きる確率は \(2|T|\lceil\log_2|T|\rceil\left(\frac{|T|-1}{P}\right)^K\) 以下です。
例えば \(|T|=10^6,P\gt10^9,K=10\) の場合、衝突の確率は \(10^{-20}\) 未満と見積もることができます。
余談ですが、次のように LCP array と sparse table（または segment tree）を使用した決定的なアルゴリズムも存在します。計算量は \(O(|S|\log|S|)\) です。
投稿日時:
最終更新: