AT_abc285_b [ABC285B] Longest Uncommon Prefix

[problemUrl]: https://atcoder.jp/contests/abc285/tasks/abc285_b 英小文字からなる長さ $ N $ の文字列 $ S $ が与えられます。 $ S $ の $ x $ 文字目 $ (1\ \le\ x\ \le\ N) $ は $ S_x $ です。 $ i=1,2,\dots,N-1 $ それぞれについて、以下の条件を全て満たす最大の非負整数 $ l $ を求めてください。 - $ l+i\ \le\ N $ である。 - 全ての $ 1\ \le\ k\ \le\ l $ を満たす整数 $ k $ について、 $ S_{k}\ \neq\ S_{k+i} $ を満たす。 なお、 $ l=0 $ は常に条件を満たすことに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S $

$ N-1 $ 行にわたって出力せよ。そのうち $ x $ 行目 $ (1\ \le\ x\

### 制約 - $ N $ は $ 2\ \le\ N\ \le\ 5000 $ を満たす整数 - $ S $ は英小文字からなる長さ $ N $ の文字列 ### Sample Explanation 1 この入力では、 $ S= $ `abcbac` です。 - $ i=1 $ のとき、 $ S_1\ \neq\ S_2,\ S_2\ \neq\ S_3,\ \dots\ ,S_5\ \neq\ S_6 $ であるため、 最大値は $ l=5 $ です。 - $ i=2 $ のとき、 $ S_1\ \neq\ S_3 $ ですが $ S_2\ =\ S_4 $ であるため、 最大値は $ l=1 $ です。 - $ i=3 $ のとき、 $ S_1\ \neq\ S_4,\ S_2\ \neq\ S_5 $ ですが $ S_3\ =\ S_6 $ であるため、 最大値は $ l=2 $ です。 - $ i=4 $ のとき、 $ S_1\ =\ S_5 $ であるため、 最大値は $ l=0 $ です。 - $ i=5 $ のとき、 $ S_1\ \neq\ S_6 $ であるため、 最大値は $ l=1 $ です。