Z-Algorithm Bash(Beta)編（paizaランク B 相当）

前回までで、最長共通接頭辞の性質を利用した効率的な Z 配列の計算方法について学びました。あとは、各左端に対して、Z 配列の値を求める際に、最長共通接頭辞の性質を利用して Z 配列を効率的に更新していけば、Z 配列を非常に効率的に求めることができます。このように、最長共通接頭辞の性質を利用して時間計算量 O(|s|) で計算するアルゴリズムを Z-Algorithm といいます。

では、実際に Z-Algorithm を実装してみましょう。
Z 配列を求める単純なアルゴリズムは以下のようなものでした。

for i = 0 から |s| - 1 まで:
    while i + z[i] < |s| かつ s[z[i]] == s[i + z[i]]:
        z[i]++;

ここで、Z 配列を求める途中段階において、今まで見た最長共通接頭辞の中で右端 j + z_j が最大のものをフロンティアと呼び、その左端を j とします。

このとき、Z-Algorithm は、

1. もしフロンティアが i 番目の文字を覆っていれば (i < j + z_j)、最長共通接頭辞の性質を使って暫定的な z_i を求める
2. もし、i 番目の文字から始まる最長共通接頭辞の右端 i + z_i がフロンティアの位置 j + z_j と一致している場合のみ、Z 配列を再計算してフロンティアを更新する

という非常にシンプルなアルゴリズムになります。

具体的な疑似コードは以下のようになります。

j = 0
for i = 0 から |s| - 1 まで:
    if j != 0 かつ i < j + z[j]:
        z[i] = min(z[i - j], j + z[j] - i)
    if j == 0 または j + z[j] <= i + z[i]:
        while i + z[i] < |s| かつ s[z[i]] == s[i + z[i]]:
            z[i]++;
        j = i

j = 0 のときは最長共通接頭辞が文字列全体に一致してしまうため、フロンティアの最長共通接頭辞を利用することができないことに注意してください。

では、Z-Algorithm を実装してみましょう。
文字列 s が与えられるので、s の Z 配列をすべて求めてください。