← 返回题目列表

AtCoder · abc285_b

D. 最长的不常见前缀

中文机器翻译题面 查看原题

分数: 200 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母组成。 的 x-th (1 \le x \le N) 的字符 S is S_x.

对于每个 i=1,2,\dots,N-1,找到最大非负整数 l 满足以下所有条件:

  • l+i \le N,和
  • 对于所有整数 k 这样 1 \le k \le l,它认为 S_{k} \neq S_{k+i}.

请注意 不包括 l=0 始终满足条件。

约束

  • N 是一个整数,使得 2 \le N \le 5000.
  • S 是一个长度为的字符串 N 由小写英文字母组成。

输入

输入由标准输入按以下格式给出:

N
S

输出

打印 (N-1) 行。 的 x-th (1 \le x < N) 行应包含整数答案 i=x.


示例输入 1

6
abcbac

示例输出 1

5
1
2
0
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.