k-substrings

题意翻译

## 题目描述 给定一个长度为 $n$ 的字符串 $T$ 。 定义 $k$ 子串表示 $S_k , S_{k+1} ~ \cdots S_{n - k +1}$ 。显然的， $1$子串= $T$，并且有 $\lceil \frac n 2 \rceil$ 个 $k$ 子串。 对于每一个 $k$ 子串 $k=1,2,3...\lceil \frac n 2 \rceil$ ，试找出最大长度的字符串 $t$，使得 $t$ 是 $T$ 的前缀和后缀且 $t$ 的 长度为奇数。 ## 输入输出格式 ### 输入格式： 输入的第一行是一个整数 $n$，表示字符串的长度。 输入的第二行是一个长度为 $n$ 的字符串。 ### 输出格式： 输出 $\lceil \frac n 2 \rceil$ 个数，其中第 $i$ 个数为 满足 $t$ 是 $i$ 子串的前缀和后缀的字符串 $t$ 的最大长度。 翻译贡献者：@[misinclair](https://www.luogu.com.cn/user/46749)

题目描述

You are given a string $ s $ consisting of $ n $ lowercase Latin letters. Let's denote $ k $ -substring of $ s $ as a string $ subs_{k}=s_{k}s_{k+1}..s_{n+1-k} $ . Obviously, $ subs_{1}=s $ , and there are exactly  such substrings. Let's call some string $ t $ an odd proper suprefix of a string $ T $ iff the following conditions are met: - $ |T|>|t| $ ; - $ |t| $ is an odd number; - $ t $ is simultaneously a prefix and a suffix of $ T $ . For evey $ k $ -substring () of $ s $ you have to calculate the maximum length of its odd proper suprefix.

输入输出格式

输入格式

The first line contains one integer $ n $ $ (2<=n<=10^{6}) $ — the length $ s $ . The second line contains the string $ s $ consisting of $ n $ lowercase Latin letters.

输出格式

Print  integers. $ i $ -th of them should be equal to maximum length of an odd proper suprefix of $ i $ -substring of $ s $ (or $ -1 $ , if there is no such string that is an odd proper suprefix of $ i $ -substring).

输入输出样例

输入样例 #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

说明

The answer for first sample test is folowing: - 1-substring: bcabcabcabcabca - 2-substring: cabcabcabcabc - 3-substring: abcabcabcab - 4-substring: bcabcabca - 5-substring: cabcabc - 6-substring: abcab - 7-substring: bca - 8-substring: c