Description
Input
输入分为两行,第一行为一个整数,表示字符串的长度,第二行有个连续的小写的英文字符,表示字符串的内容。
Output
输出文件只有一行,即:输入数据中字符串的最长双倍回文子串的长度,如果双倍回文子串不存在,则输出0。
Sample Input
16 ggabaabaabaaball
Sample Output
12
HINT
N<=500000
/* 先跑一遍manacher,p[i]表示对称轴为i和i+1之间位置的最长回文串长度的一半,由于只求一种对称情况,所以不用加入无关字符。 枚举x为对称轴,实际上对称轴在x到x+1之间,如果len(x+1,y)*4能更新最后的答案,需要满足y-p[y]<=x且y<=x+p[x]/2,按照y-p[y]排序一下,递推x的时候将符合1式的y插入set,在set中查找x+p[x]/2的前驱更新答案即可。*/#include#include #include #include #define N 500010#define lon long longusing namespace std;int n,p[N],q[N],ans;char ch[N];set t;void manacher(){ int mx=0,id; for(int i=1;i<=n;i++){ if(mx>=i) p[i]=min(mx-i,p[id*2-i]); else p[i]=0; while(ch[i+p[i]+1]==ch[i-p[i]]) p[i]++; if(p[i]+i>mx) id=i,mx=p[i]+i; }}bool cmp(int a,int b){ return a-p[a]