← 返回题目列表

Codeforces · 961/F

F. k 子串

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

给定一个由 n 个小写拉丁字母组成的字符串 s。

让我们将 s 的 k 子串表示为字符串 subsk = sksk + 1..sn + 1 - k。显然,subs1 = s,正好有$$\left\lceil \frac{n}{2} \right\rceil$$这样的子串。

让我们将某个字符串 t 称为字符串 T 的奇数真前缀,当且仅当满足以下条件:

- |T| > |t|;
- |t|是奇数;
- t 同时是 T 的前缀和后缀。

对于 s 的每个 k 子串 ($$k \in [1,\left\lceil \frac{n}{2} \right\rceil]$$) ,您必须计算其奇数真上前缀的最大长度。

输入

第一行包含一个整数 n (2 ≤ n ≤ 106) — 长度 s。

第二行包含由n个小写拉丁字母组成的字符串s。

输出

打印 $$\left\lceil \frac{n}{2} \right\rceil$$ 整数。其中第 i 个应该等于 s 的 i 子串的奇数真上前缀的最大长度(或者 - 1,如果不存在这样的字符串是 i 子串的奇数真上前缀)。

示例

输入 #1

15
bcabcabcabcabca

输出 #1

9 7 5 3 1 -1 -1 -1

输入 #2

24
abaaabaaaabaaabaaaabaaab

输出 #2

15 13 11 9 7 5 3 1 1 -1 -1 1

输入 #3

19
cabcabbcabcabbcabca

输出 #3

5 3 1 -1 -1 1 1 -1 -1 -1

注意

第一个样本测试的答案如下:

- 1-子字符串:bcabcabcabcabca
- 2-子串:cabcabcabcabc
- 3 个子字符串:abcabcabcab
- 4 个子串:bcabcabca
- 5-子串:cabcabc
- 6 个子串:abcab
- 7 个子串:bca
- 8 个子串:c