最長共通接頭辞の性質を用いて Z 配列を求める Bash(Beta)編（paizaランク C 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
前回の問題の文字列には $ が含まれていましたが、$ が含まれていない場合や文字列の一部が繰り返されている場合はどうなるでしょうか。
たとえば、'abababab' という文字列を考えてみます。この文字列についても前半の Z 配列と後半の Z 配列は同じになりそうな気がしますね。しかし、実際の Z 配列は〈8, 0, 6, 0, 8, 0, 6, 0〉とはなりません。これは、うしろから x 番目の Z 配列の値が x 以下になるからです。実際、この文字列の Z 配列は〈8, 0, 6, 0, 4, 0, 2, 0〉 となります。
この性質を利用して、Z 配列を求めてみましょう。
文字列 s と、s の m 文字目までの Z 配列が与えられます。s は、z_m = |s_{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 ≦ |s|
・ 0 ≦ z_i ≦ |s| (1 ≦ i ≦ m)
・ s は英小文字のみからなる文字列
・ z_m = |s_{m, |s|}|
- 入力例1
-
abcabcabcabc
7
12 0 0 9 0 0 6
- 出力例1
-
12
0
0
9
0
0
6
0
0
3
0
0
