短い文字列の Z 配列 Java編（paizaランク B 相当）

この問題集のゴールは、文字列 s が与えられたときに、s の各部分文字列 s_{i, |s|} の最長共通接頭辞の長さをすべて求めることです。i 番目に s と s_{i, |s|} の最長共通接頭辞の長さを並べた配列を Z 配列と呼びます。

まずは簡単な例を考えてみましょう。
文字列 'aaabb' なら、文字列の 1 文字目から始まる部分文字列は文字列そのものなので 5 に, 2 文字目から始まる部分文字列は 'aabb' なので 2 に, 3 文字目から始まる部分文字列は 'abb' なので 1 に, 4 文字目から始まる部分文字列は 'bb' なので 0 に, 5 文字目から始まる部分文字列は 'b' なので 0 になります。よって、この文字列の Z 配列は〈5, 2, 1, 0, 0〉となります。

では、与えられた文字列の Z 配列を求めてみましょう。
文字列 s が与えられるので、各 i = 1, 2, ..., |s| について、s と s_{i, |s|} の最長共通接頭辞の長さ z_i を求めてください。