heno239’s blog

まとめたいことをまとめる

動的 (online) Z_algorithm 覚え書き

  • Z_algorithmとは

長さnの文字列Sに対し、次のような数列{a_i}{0<=i<n}をO(n)で構築できる:

・S_iをSのi番目以降からなる文字列としたとき、SとS_iの最大共通接頭辞の長さがa_i

 

世界中で説明されてると思うので、ここでは詳しく触れません

 

  • 動的

計算量にlogを1つ増やすことで動的にすることができます。(普通に線形で出来ます。)

具体的には、「後ろへの文字の追加」と「現在のa_iの値を出力する」などができます(文字の変更は厳しい)。

 

  • やり方

 

以下、「iが条件を満たす」とは「S_iがSのprefixとなる」ことを表すことにします。

 

 step1. 現在の文字列の長さをnとしたとき、条件を満たすiの集合Aと、そうでない集合Bを分ける。

 

 step2. 一度Bに入ったものは二度とBから出てこない。AからBに移動する、すなわち新しい文字の追加によって条件を満たさなくなるようなiの集合を高速に求めたい。

 

 (以下、便宜上i=0はAに含まないことにします。)

 

 step3. まず、Aに属するもののうち、新文字の追加後もiが条件を満たすような最小のiを求める。(後述の実装例のLine 25~31にあたる。)

 

 step4. step3で求めた最小のiをxとする(存在しなければstep4は不要)。

いま、x<iを満たすi∈Aで、新文字追加後に条件を満たさなくなるiを求めたい。

 

ここで、S_xはSのprefixであることから、(Sの長さをlenとすると)求めたいiの集合というのは、Sのlen-x-1番目の文字を追加したときにAから削除したiの集合と一致する。(

例.

ababcababにcを追加するとき、追加前はAに{5(abab),7(ab)}が含まれている。ababcはababcababcのprefixになるので、step3でx=5になる。

 

ここで新7(abc)がababcababcのprefixになるかのcheckが必要だが、このcheckは新7(abc)が新x=5(ababc)のprefixになるかのcheckとまったく同じ。

 

そして新7が新5のprefixになるかどうかのcheckは、5文字さかのぼった時代(ababcの時代)の旧2(abc)が旧0(ababc)のprefixになるかどうかのcheckと同じ。

 

したがって、ababcの時代にcheckでダメになった旧2(abc)を呼び起こすことで、現代でも新7(abc)がダメになることがわかる。

 )

 

こんな感じで、ダメになるものたちを(過去の記憶を呼び起こすことで)列挙できる。

step4は、実装例のLine 32~37と、del関数で行っている処理に該当する。

 

  • 実装例 

online Z algorithm

  • 実装例(追記)

普通にlogつけずにできます。

O(N)

  • verify

https://judge.yosupo.jp/submission/14910

  • 例題

https://codeforces.com/gym/102341/problem/K

  • 参考文献

https://gist.github.com/snuke/84ca11fc3f1ab109a3d30a006afcfa1b

 

 

 

  • 虚無枠

いかがでたしか?