文字列アルゴリズムによる部分文字列照合テクニック
このサイトが詳しい。
次のような問題を考える。
文字列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
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文字以上の接頭辞が一致してるため)、そうでないのならば一致していない。
計算量は
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の計算式から、このままでは倍されたものであるとわかる。(はローリングハッシュの基数)Rolling Hashが素数でModを取ってる時、逆元を使って区間のHash値を求められる。
これならば、計算量はになる。
随時加筆