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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961F/a53370bfcdd8093b84a167b7bb5ebbbbde89cfc8.png) 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 (![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961F/0db45c1fd47a0828e7ef646cf910ebdb4ed26cf3.png)) 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 ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF961F/a53370bfcdd8093b84a167b7bb5ebbbbde89cfc8.png) 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