はじめに
見た瞬間に「あ、ローリングハッシュだ」と思ったものの、「実装どうするんだっけ…」で1時間椅子を温めました。ライブラリ貼り付けで済むならまだしも、ちょっといじろうとすると手になじませる必要がありそうなので、記事にしつつ理解を深めようと思います。
2023/1/8 19時ごろ追記:公式解説の通り後半を反転させる方が実装は楽ですね。まあ部分ハッシュを考えるというアイデアはどこかで活かせそうなのでこれはこれ、ということで。
問題
ACコード
前提知識
ローリングハッシュ
https://qiita.com/hirominn/items/80464ee381c8d400725f
考察
さて、本問題ではTには左の文字列・真ん中の文字列（以下M）・右の文字列の3つの文字列が存在していますが、
左の文字列と右の文字列を結合した文字列（以下X)と、Mが一致するものが存在するかを問われている問題です。
愚直にやるのであれば、分割位置をずらしながら確認していくことになりますが、
1回ずらすごとに生成された長さNの文字列同士を一文字ずつ確認していくことになるので、O(N**2)になり間に合いません。
この文字列に対してハッシュを取ることで、文字列同士の一致を確認することを考えます。
まずは文字列Mについては、Tを反転させて考えるとローリングハッシュをそのまま適用でき、
1文字ずつずらした文字列のハッシュ列をO(N)で生成することができます。
次に、文字列Xについて考えます。
ここも工夫をするとハッシュを効率よく計算することが出来ます。
まず、ローリングハッシュの算出式を眺めてみます。
ローリングハッシュ算出用の素数をB,Mとし、
文字列Sに対するローリングハッシュ関数H(S)は以下のようになります。
H(S)=(S_1B^{N-1}+\cdots+S_{N-1}B^{1}+S_{N}) \ mod \ M
さて、具体的にN=4で、結合文字列Xに対してハッシュを計算します。
H(X)=(X_1B^{3}+X_2B^{2}+X_3B+X_{4}) \ mod \ M
さらに、LをTの前半N文字、RをTの後半N文字とすると、問題文中のiを変化させていったときのH(X)は下記の通りになります。
(L_1B^{3}+L_2B^{2}+L_3B+L_{4}) \ mod \ M\\
(L_1B^{3}+L_2B^{2}+L_3B+R_{4}) \ mod \ M\\
(L_1B^{3}+L_2B^{2}+R_3B+R_{4}) \ mod \ M\\
(L_1B^{3}+R_2B^{2}+R_3B+R_{4}) \ mod \ M\\
(R_1B^{3}+R_2B^{2}+R_3B+R_{4}) \ mod \ M\\
LとRと部分を足すことができるので、それぞれ個別に算出します。
\begin{align}
(&L_1B^{3}+L_2B^{2}+L_3B+L_{4}&) \ mod \ M\\
(&L_1B^{3}+L_2B^{2}+L_3B&) \ mod \ M\\
(&L_1B^{3}+L_2B^{2}&) \ mod \ M\\
(&L_1B^{3}&) \ mod \ M\\
\end{align}
\begin{align}
(&&&&+R_{4}) \ mod \ M\\
(&&&+R_3B&+R_{4}) \ mod \ M\\
(&&+R_2B^{2}&+R_3B&+R_{4}) \ mod \ M\\
(&R_1B^{3}&+R_2B^{2}&+R_3B&+R_{4}) \ mod \ M\\
\end{align}
※うまく整形できない…
これらは累積的に実行することで、O(N)で算出可能で、ローリングハッシュの部分ハッシュみたいなものが生成できます。
最後に、上記部分ハッシュから生成されたXのハッシュ列とMのハッシュ列が一致するかを確認すればＯＫです。
各計算はO(N)で実行可能なので、全体としてもO(N)になります。
おわりに
ハッシュを部分的に算出できる、というのは面白い性質だなと思いました。
可能ならコンテスト中に解ききりたかったですが、苦労した分忘れないと思うので次に生かしたいと思います。