動的 (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関数で行っている処理に該当する。
-
実装例
-
実装例(追記)
普通にlogつけずにできます。
-
verify
https://judge.yosupo.jp/submission/14910
-
例題
https://codeforces.com/gym/102341/problem/K
-
参考文献
https://gist.github.com/snuke/84ca11fc3f1ab109a3d30a006afcfa1b
-
虚無枠
いかがでたしか?