はじめに 名前がかっこいい。 codeforcesにある解説を試してみる。 Z algorithmとは 文字列Sと部分文字列S[i..]の最長共通接頭辞数をZ[i]とし、すべてのiについて、それをO(n)で求めるアルゴリズム 単純な方法だとO(n^2) 1996,97年あたりにGusfieldによって提案された アルゴリズム うまく過去の情報をメモしておいて計算量を減らす。 iのZ-boxを範囲[i, i+Z[i]-1]と定義する あるiについて、i以下のjについてZ-boxを考え、 Z-boxの終点で最も右側にあるものをr_i、そのr_iのペアとなるZ-boxの始点をl_iとする Z[k]を求めるときは、過去のZとr_{k-1}とl_{k-1}があれば求められる k>rの場合 rを超えてるので、新しくkでのZ-boxを考える必要があるので、部分文字列S[k..]の接頭辞を比較する k=l