Senの競技プログラミング備忘録

こけた問題を自分用の解説で載せる。けんちょんさんのブログを目指したい。質的にも量的にも。こけた問題だけに限定するけど

文字列アルゴリズムによる部分文字列照合テクニック

このサイトが詳しい。

drken1215.hatenablog.com

次のような問題を考える。


文字列S(|S| <= 5000)が与えられ、次のq(q <= 5 * 10^5)回のqueryに答えよ。

  • a, b, rが与えられて、S[a, a + r], S[b, b + r]が同じ連続部分文字列かどうかを判定せよ。

いい感じに前処理をして、クエリ1回ごとにかかる計算量O(1)とかO(log N)でなければいけない。
これは、有名な文字列アルゴリズムたちを使って、こう解くことができる。

(Suffix Arrayをしっかり理解できたら、また加筆する。)

Z-algorithm

sen-comp.hatenablog.com

Z-algorithmは、与えられた文字列Sについて、「その場所から最後までとした連続部分列とSの共通接頭辞の長さ」が求まる。この性質をうまく利用して考える。
ちなみにすべて0-idx。

S="abcde"とする。
SP[0]="abcde"
SP[1]="bcde"
SP[2]="cde"
SP[3]="de"
SP[4]="e"
として、これらすべてにZ-algorithmを適用させて、結果の配列を求めておく。
そして、S[a, a + r], S[b, b + r]について一致はつぎのように考える。(ここでは、a < bと考える)


S[a]から始まるSPの文字列、つまりSP[a]のZ-algorithmの結果をRとする。
SP[a]でS[b]に相当する場所のRの結果は、S[a]から始まる連続部分文字列と、S[b]から始まる連続部分文字列の一致する接頭辞の長さ。
この長さがr以上ならば、一致していて(r文字以上の接頭辞が一致してるため)、そうでないのならば一致していない。
計算量は O(N^2+q)

Rolling Hash

Rolling Hashについては、このサイトなどが詳しいと思う。

S="abcde"とする。
SP[0]="abcde"
SP[1]="bcde"
SP[2]="cde"
SP[3]="de"
SP[4]="e"
について、それぞれの文字列の何文字目までのHash値を計算しておく。


S[a,a + x]とS[b, b + x]が一致するときの最大のxを二分探索で求めてみる。
値の一致判定は、SPから計算したHash値のテーブルから判定できる。(xを増やしていくと、ある境界より上では、S[a, a + x]とS[b, b + x]のHash値が一致しない)
計算量は[tex: O(N^2 +q\log(N))]

また、SPの計算を省くこともできる。文字列SのままHash値を計算して、累積和のように、減算して区間を切り出せばよい。ただし、この場合、S[i, j]を切り出したとすると、Rolling Hashの計算式から、このままでは b^i倍されたものであるとわかる。( bはローリングハッシュの基数)Rolling Hashが素数でModを取ってる時、逆元を使って区間のHash値を求められる。
これならば、計算量は O(N + q \log(N))になる。

随時加筆