Main-Lorentz　Algorithm

概要

文字列のrunを $O(N log N)$ で列挙することができるアルゴリズム
runは文字列内に現れる部分文字列の繰り返しのことで、特に長さが極大で周期が最小のものを指すっぽい
情報としては区間と周期を持ち、実際に使うときは(l, r, period)としてs[l, r)の周期がperiodみたいに持つ
注意するべきなのは、繰り返しはピッタリである必要はなくて(r - l) % period != 0でもよい
ただしr - l >= 2*periodであるもののみを考える

例

"mississippi"

区間: [1, 8), period: 3

長さ3の"iss"が7/3周期分ある

s[0] != s[0+period(= 3)] かつ s[8] != s[8-period(= 5)]だからこれ以上伸ばせなくて長さが極大である

あとは周期1で2周期分のやつが3つあるけどまあ自明なのではい

$O(N)$ アルゴリズムもあるっぽいけど実際に使うなら $O(N log N)$ で十分だから、いいよね
$O(N log N)$ があれば実用上大体十分な文字列アルゴリズムって、あるじゃん(例: Suffix Array)

アイデア

基本的には分割統治がメインアイデアになっていて、それぞれの深さについて左側と右側の境界をまたぐようなrunだけ考える

例

"abcbcd"

"abc | bcd" みたいに左右で分ける

" ab [c] | bcd " みたいに "c" が周期になり、またぐやつを探す

" a [bc] | bcd " みたいに "bc" が周期になり、またぐやつを探す

" a [bc | bc] d" がまたいでいて周期が2以上あるのでrun

" [abc] | bcd " みたいに "abc" が周期になり、またぐやつを探す

このように、中心をまたぐrunを境界の左側の部分文字列が周期になるようなものだけを探すを繰り返す
そして見つけていくときにそれが極大であることを確認し、その区間のrunの周期で現時点で最小なら更新する
極大であることの確認は、上の"mississippi"の例の極大の確認の仕方をやればよい
すると極大かつ周期が最小のものだけが見つかる
例では左側しか見てないが、実際には右側の部分文字列が周期となるものも考える必要があって文字列をreverseしてよしなにやると楽

ある文字列について、runの総数はそれぞれの分割統治の深さについて $O(N)$ 個、深さが $O(log N)$ 個(修正しました 11/28 17:36)なので全部で $O(N log N)$ 個に収まることがわかる
なんかいい感じの論文を読むと普通に $O(N)$ 個であることが多分わかる(まあそうじゃないと $O(N)$ アルゴリズム、ないよね)

中心をまたぐrunの見つけ方

ところで、それぞれの深さについて $O(N)$ で跨ぐようなやつを求めるのはどうやるの？という気持ちになるのでそれを説明する
その要になるのがZ algorithmで、うまく使うとうまくいける

Z algorithmって、なに？

それぞれのsuffixがもとの文字列とprefixが何文字一致しているか
文字列sについて、Z algorithmで求められるものを z[i] とする
すると、 s[i, i+z[i]) == s[0, z[i]) && s[i+z[i]] != s[z[i]] が成り立つ

例

s = "a b c b c d"(空白は無視)
z = {6,0,0,0,0,0}

わからせる気のない例

これを周期を求めるのにうまく使いたくて、繰り返し、文字列、アルゴリズムみたいなことを考えると(K)MPが思いつくけどなんかZ algorithmでもよい
結果だけ言うと、 s[0, i+z[i]] が周期 i の繰り返しになっている(ただし最小とはいっていない)
ただ、周期 i が最小じゃないとき、最小となるべき j < i を見るとき既に考えているはずなので大丈夫

Z algorithmを使って、どうなるの？

s[i, m) を周期とするrunを探そうとしているときs[0, i) のSuffixと s[m, |s|)のprefixにいくつ繰り返しがあるかを知りたい
s[0, i)のsuffixについては、 s[0, m) をreverseしたものに対してZ algorithmを適用する
そうすると、s[i-1]に対応する位置の値を見ることで周期を m-iとする繰り返しがどこまで続いているかがさっきのやつからわかる

s[m, |s|)のprefixについては、 t = s[m, |s|) + '#' + sを考えてZ algorithmを適用する('#'は実際には必要ない)
そして後ろ側につけたs の s[i] に対応する場所の値をみることで周期を m-i とする繰り返しの長さがわかる

例(とても見にくい)

s = "missis | sippi"

rev("missis") = "s i s s i m"
z1 = {6, 0, 1, 2, 0, 0}

"sippi" + '#' + s = "s i p p i # m i s s i s s i p p i"
z2 = "17, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 5, 0, 0, 0, 0"

この時、"sis"を周期とするものが最適なのでそのときどうなるかを見てみる

左側について、z1[3]を見ると2なので、周期3で長さが5であることがわかる

左側は周期とする部分文字列自体があるのでその分の長さである3を加える

右側について、z2[9]を見ると2なので、周期3で長さが2であることがわかる

z2[9]は#の右側で"sis"の先頭に対応している

よって左側と右側を合わせることで周期3で長さが7であるものが見つかった

これを左側の全部のsuffixについて行えばよい
最初に行うZ algorithmもその後の計算も $O(N)$ なので、分割統治のある深さについて全部足しあわせても $O(|S|)$ で収まるので大丈夫

ここまでを実装すると、できる
添字がごちゃごちゃして辛くなったので頑張ってください

https://judge.yosupo.jp/problem/runenumerate
ここでverifyとACコードの確認ができる

例題

計算量は明らかに駄目なんだけどなんか十分な速さで通ったし他の解法よりは速いので...

ICPC Asia Hua-Lian Regional 2017 L - Finding the Bases

ある文字列Sが与えられる。
その文字列の部分文字列がある文字列Tをいくつかつなげたものになっている時、その部分を圧縮してTにすることができる
既に圧縮した部分文字列を含む部分文字列をもう一度圧縮することはできない
最適に圧縮した時長さを最小で何にできるか

|S| <= 10000
T <= 10

通している人の多くはKMPでループを見つけてやるみたいな $O(N^2 * T)$ 解法で、めっちゃギリギリなんだけどすこしうまくやって早くすることでなんとか通る
runの列挙を用いて通すには、(l, r, period)をまずl <= i < r && r-i >= periodとなるiについて(i, r, period)をrunに追加する
そしたら単純にDPをすることができるので通る
最初のrun列挙に $O(N log N)$ 、runの数は $O(N)$ に抑えられるので展開すると $O(N^2)$ になる
DPの遷移はそれぞれのrunについてdp[i + l + k*period] = dp[i] + 1 みたいにkをループで回す必要があり、すべてのrunについて考えると $O(N^3)$
余裕でこう考えると間に合わなくなってしまうんだけど、まあrun同士の被りとかがうまいことになって減るので早くなる
ただし、最悪ケースでは $O(N^2)$ ぐらいは必要になるけどテストケースの弱さとか色々期待すると通る