#2579. 「SHOI2011」双倍回文

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

记字符串 x 的倒置为 x^R ,例如 \texttt{abcd}^R=\texttt{dcba}, \texttt{abba}^R=\texttt{abba}
对字符串 x ,如果 x 满足 x^R=x ,则称之为回文;例如 \texttt{abba} 是一个回文,而 \texttt{abcd} 不是。
如果 x 能够写成 ww^Rww^R 的形式,则称它是一个「双倍回文」。换句话说,若要 x 是双倍回文,它的长度必须是 4 的倍数,而且 x x 的前半部分、 x 的后半部分都要是回文。例如: \texttt{abbaabba} 是一个双倍回文,而 \texttt{abaaba} 不是,因为它的长度不是 4 的倍数。
x 的子串是指在 x 中连续的一段字符所组成的字符串。例如 \texttt{bc} \texttt{abcd} 的子串,而 \texttt{ac} 不是。
x 的回文子串,就是指满足回文性质的 x 的子串。
x 的双倍回文子串,就是指满足双倍回文性质的 x 的子串。
你的任务是,对于给定的字符串,计算它的最长双倍回文子串的长度。

输入格式

输入分为两行,第一行为一个整数 ,表示字符串的长度,第二行有 个连续的小写的英文字符,表示字符串的内容。

输出格式

输出只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。

样例

样例输入 1

16
ggabaabaabaaball

样例输出 1

12

样例输入 2

24
googlegooglegooglegoogle

样例输出 2

0

数据范围与提示

数据编号 数据限制
1 n=1500
2 n=2500 ,答案不超过 1500
3 n=5000 ,答案不超过 1500
4 n=10000 ,答案不超过 1500
5 n=25000
6 n=50000
7 n=75000
8 n=10^5
9 n=2.5\times 10^5
10 n=5\times 10^5