Score : $200$ points

问题描述

你将得到一个长度为 $N$ 的由小写英文字母组成的字符串 $S$。其中，第 $x$ 个（$1 \le x \le N$）字符记为 $S_x$。

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

• $l+i \leq N$，且
• 对于所有满足 $1 \leq k \leq l$ 的整数 $k$，均有 $S_{k} \neq S_{k+i}$。

注意：$l=0$ 总是满足上述条件。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a string $S$ of length $N$ consisting of lowercase English letters. The $x$-th $(1 \le x \le N)$ character of $S$ is $S_x$.

For each $i=1,2,\dots,N-1$, find the maximum non-negative integer $l$ that satisfies all of the following conditions:

• $l+i \le N$, and
• for all integers $k$ such that $1 \le k \le l$, it holds that $S_{k} \neq S_{k+i}$.

Note that $l=0$ always satisfies the conditions.

Constraints

• $N$ is an integer such that $2 \le N \le 5000$.
• $S$ is a string of length $N$ consisting of lowercase English letters.

Input

The input is given from Standard Input in the following format:

$N$

$S$

Output

Print $(N-1)$ lines. The $x$-th $(1 \le x < N)$ line should contain the answer as an integer when $i=x$.

Sample Input 1

6
abcbac

Sample Output 1

5
1
2
0
1

In this input, $S=$ abcbac.

• When $i=1$, we have $S_1 \neq S_2, S_2 \neq S_3, \dots$, and $S_5 \neq S_6$, so the maximum value is $l=5$.
• When $i=2$, we have $S_1 \neq S_3$ but $S_2 = S_4$, so the maximum value is $l=1$.
• When $i=3$, we have $S_1 \neq S_4$ and $S_2 \neq S_5$ but $S_3 = S_6$, so the maximum value is $l=2$.
• When $i=4$, we have $S_1 = S_5$, so the maximum value is $l=0$.
• When $i=5$, we have $S_1 \neq S_6$, so the maximum value is $l=1$.

update @ 2024/3/10 11:55:10