【柠檬的密码】

题目描述

Lemon 觉得他需要一个复杂的密码来保证他的帐号的安全。他经过多日思考,决定使用一个长度为奇数的回文串来作为他的密码。

但是这个回文串太长了,Lemon 记不住,于是 Lemon 决定把它记在本子上。当然直接把密码明文记录实在太愚蠢了,于是 Lemon 决定在记录时加入一些无意义的字符以保证密码的安全。

具体来说,假设 Lemon 的密码串是 S ,Lemon 选择了一个不超过 len(S)/2 的正整数x,然后把 S 的前 x 个字符组成的字符串设为 Left,把 S 的后 x 个字符组成的字符串设为 Right,把 S 其余的字符组成的字符串设为 Mid 。

Lemon 实际记录在密码本上的内容是 A+Left+B+Mid+C+Right。 其中 A,B,C 都是无意义的字符串(有可能是空串)。他觉得这样就很安全了。

某一天,Melon 无意发现了 Lemon 的笔记本,并发现了这个字符串。Melon 决定把 Lemon 的密码破解出来。但是显然有不计其数的可能密码。

Melon 认为,Lemon 的密码一定很长,于是他想知道,这个字符串里隐藏的最长可能的密码有多长呢?

输入格式

输入数据第一行包含一个正整数 N ,表示字符串的长度。
数据第二行包含一个长度为 N 的字符串,仅由小写字母组成,表示需要破译的字符串。

输出格式

输出数据仅包含一个整数,表示最长可能的密码的长度。

样例数据 1

输入

25
orzabcdxyzefgfeqwertydcba

输出

13

备注

【样例说明】
最长的可能的密码是“abcdefgfedcba”,长度为 13 。
Lemon 选择的 x=4
Left=”abcd”
Right=”dcba”
Mid=”efgfe”
A=”orz”
B=”xyz”
C=”qwerty”

【数据范围】
对于 20% 的数据,满足N<=20
对于 40% 的数据,满足N<=300
对于 60% 的数据,满足N<=2000
对于 100% 的数据,满足N<=100000

比较萎的一道题。。。先对整个串跑一遍Manacher,然后把串反着建KMP一遍看两边的最大匹配,f[i]代表到i为止的最大回文串长度(一边的),最后判断有没有交集的时候要从i+rad[i]后和i-rad[i]前来判断。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*