Description
Input
输入分为两行，第一行为一个整数，表示字符串的长度，第二行有个连续的小写的英文字符，表示字符串的内容。
Output
输出文件只有一行，即：输入数据中字符串的最长双倍回文子串的长度，如果双倍回文子串不存在，则输出0。
Sample Input
16
ggabaabaabaaball
Sample Output
12
HINT
N<=500000
因该算是一道挺不错的题，需要仔细思索一下
首先我可以看出：
（1）我们找到的串的本身也是一个回文串（显然）
（2）这个回文串的长度一定是偶数（显然）
（3）左右两个串一定也是偶数长度的回文串（显然）
那么我们先用manacher处理出以每个字符为中心的回文串长度
由于我们所需处理的这些串的长度都为偶数，所以这些串的中心都在manacher时的那些填充字符上（显然）
那么我们就先枚举大串的中心i,设左边小串的中心为j
那么j+rad[j]>=i (rad[]为manacher中处理出的数组)
由于左边一定是回文串，那么rad[j]就应该要覆盖到i（不然怎么保证左边是回文串），而如果左边得到保证，那么右边也一定符合条件（对称）
所以我们就只需求出满足条件的最左侧的j
然后我们对j也有一个枚举范围，那就是在i的回文串范围内，并且还在i-rad[i]/2 ~ i 之间，不然不够
这样我们就可以初步得出一个枚举算法，那就是对于每个i，在一定范围内枚举j，找最优解
据说这个算法是可过的，但是复杂度。。。。似乎不是太乐观
于是需要优化
该优化其实也是显然的
如果我们曾枚举过一个j，它不能覆盖到当前枚举的i(也就是j+rad[j]
那么这个j，用一定不能覆盖到i+1（显然）
也就是说这个j在之后的计算中都没有用了，我们就不需要枚举了
这样我们就可以在枚举j的时候一段一段的跳，以降低复杂度
而实现这个过程，我们可以用并查集
每次都将没用的j的父亲指向j+1，然后跳到getfather（j+1）
这样就轻松完成了分段跳这个优化
最后在分析一下复杂度
（1）manacher O（n）
（2）并查集 O（nα（n））
（3）每个点最多被删n次 O（n）
（4）每个点最多被利用一次 O（n）
（5）每个点最多被枚举一次 O（n）
这个复杂度真的是怎么算怎么舒心，而且代码很好实现！！嘿嘿
上面已经把大概的 解题思路，已经 说的很详细了，下面 就看 看 下面的代码把，这个 题 需要 用到 并查集 进行优化，否者时间超限的；
给你们一个 例子 一边更好的 理解 代码的思路：
abbaabba
? # a # b # b # a # a # b # b # a # \0
0 0 2 1 2 5 2 1 2 9 2 1 2 5 2 1 2 0 0
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#define MAX 500010
using namespace std;char s[MAX*2];
int p[MAX*2];// manacher 要生成的 数组
int f[MAX*2];// 并查集用到的 数组，里面存储 “#” 的下标void Manacher(char *s)// manacher 没有太大的 改动 可以直接套模版
{int len = strlen(s);for(int i = len; i >= 0; i--)// 这里 注意 一定要 逆序， 循环，如果赠序的 有的 s【i】 的 值会 在赋值前 被改变的 大家想想 就会清楚啦{s[2*i+2] = s[i];s[2*i+1] = '#';}s[0] = '*';int id = 0;int maxlen = 0;for(int i = 2; i <= 2*len; i++){if(id+p[id] > i)p[i] = min(p[id-(i-id)], p[id] - (i-id));elsep[i] = 1;while(s[i+p[i]] == s[i-p[i]])p[i]++;if(id+p[id] < i+p[i])id = i;maxlen = max(maxlen, p[i]);}}int getf(int x)
{if(f[x] == x)return x;f[x] = getf(f[x]);// 进行递归 从而找到 它的 根节点 （最后面的 父节点）而且 这里 在 回溯的时候 进行啦 压缩。return f[x];
}int main()
{int n;scanf("%d", &n);scanf(" %s", s);int maxlen, len, j;maxlen = 0;Manacher(s);len = strlen(s);for(int i = 1; i < len; i++){if(s[i] == '#') f[i] = i;else f[i] = i+1;}for(int i = 5; i <= len-5; i += 2){j = getf(i-p[i]/2)；// 应为 这里 是 从里 i 距离 最大处开始 查找的，所以 只要找到一个满足条件的 j 之后 就不用 在 继续 寻找啦，因为第一个找到的 这个 j 点 是长度最大 的满足。while(j < i && j+p[j] < i){f[j] = getf(j+1);// 把没有达到条件的 j 点 的父节点 往后面更新 j = f[j]; j 点 也要 更新 进行下一个循环}if(j < i) maxlen = max(maxlen, (i-j)*2);// 这里， （i-j） 表示 一个 双回文串 的 一半 的 长度（这是因为 添加啦，无关 字符的缘故，大家找一个 字符串 写一写 就清楚啦）}printf("%d\n", maxlen);return 0;
}