最長共通接頭辞の性質を用いて Z 配列を求める PHP編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
最長共通接頭辞の長さが十分ある場合、どのような性質があるかを考えてみましょう。
たとえば、'aaaa$aaaa' という文字列を考えてみます。この文字列の前半の Z 配列と後半の Z 配列はほとんど同じになりそうな気がしますね。これはなぜかというと、この文字列の 6 文字目から始まる部分文字列 'aaaa' と、この文字列全体 'aaaa$aaaa' との最長共通接頭辞の長さが 4 だからです。実際、この文字列の Z 配列は〈9, 3, 2, 1, 0, 4, 3, 2, 1〉 となります。
つまり、i 番目の Z 配列の値が s_{i, |s|} の長さにひとしいとき、残りの Z 配列の値は Z 配列の先頭から 2 番目以降の値をそのまま使えるということになります。
この性質を利用して、Z 配列を求めてみましょう。
文字列 s と、s の m 文字目までの Z 配列が与えられます。s の長さは 2 × m - 3 で、文字列 t を用いて t + '$' + t の形で表されます。
つまり、この文字列の m - 1 文字目は '$' であり、m 文字目以降は s の先頭からの繰り返しになっています。
このとき、s の Z 配列をすべて求めてください。
- 入力される値
-
s
m
z_1 z_2 ... z_m
・ 1 行目に、文字列 s が与えられます。
・ 2 行目に、与えられる Z 配列の長さを表す整数 m が与えられます。
・ 3 行目に、整数 z_1, z_2, ..., z_m が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
s の Z 配列 z_1, z_2, ..., z_|s| を改行区切りで出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 3 ≦ |s| ≦ 100000 = 10^5
・ |s| = 2 × m - 3
・ 0 ≦ z_i ≦ |s| (1 ≦ i ≦ m)
・ s は英小文字と '$' のみからなる文字列
・ s_{m - 1} = '$'
・ z_m = m - 2
- 入力例1
-
aabb$aabb
6
9 1 0 0 0 4
- 出力例1
-
9
1
0
0
0
4
1
0
0
