小G的项链（Manacher）

我看网上也没有写这个题的，顺便写一下（可能是大佬都觉得太简单了 ）
链接：牛客网

时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32768K，其他语言65536K 64bit IO Format:
%lld

题目描述

有一串有n颗珠子的项链，每颗珠子上有一个数字，从顺时针方向看依次是第1，2，…，n个珠子，第n个珠子之后是第1个珠子。但是小G觉得这串项链的造型不够美观，他决定用这串项链上的珠子造出一个新的项链，并且他希望这串新的项链是对称的。
一串项链是对称的，当且仅当存在至少一颗珠子满足：把它作为起始位置（即顺时针和逆时针方向数第0个珠子），对于任意的自然数i，顺时针数第i个珠子上的数字和逆时针数第i个珠子上的数字相同。特别的，一个仅有一颗珠子的项链也是对称的。
小G可以使用合成技术将任意正整数颗珠子合成为一个新的珠子，新珠子上的数字=原珠子上的数字的异或和。
用合成技术造出新项链的过程是这样的：最开始由小G确定一个能整除n的正整数k和一个原项链中的起始位置，之后从起始位置开始顺时针方向取连续的k个珠子，合成一个新的珠子作为新项链的第1个珠子，再取接下来连续的k个珠子，合成一个新的珠子作为新项链的第2个珠子，……，直到取完原项链的所有珠子为止。注意，合成的新珠子会直接放到新项链的位置，并不会插入原项链之中参与之后合成过程。新项链同样满足从顺时针方向看依次是第1，2，…，n个珠子，第n个珠子之后是第1个珠子。
小G希望新的项链上的珠子尽可能多，问新项链上的珠子最多有多少个。

输入描述:

第一行一个整数n。
第二行n个整数，第i个整数ai代表原项链上第i个珠子上的数字。

输出描述:
共一行一个整数，代表新项链的最大珠子数量。
示例1
输入

5
9 3 9 1 1

输出

5

示例2
输入

9
7 8 6 5 4 3 1 2 15

输出

3

备注:
1 ≤ n ≤ 2 x 105,0 ≤ ai ≤ 109
题意：
给你n个数组成环，分成k个等长的区间，每个区间的值就是区间内部数的异或和，用区间的相对位置摆成环，且使这个环组成回文串，问你回文串最长是多少？
题解：
因为n个数组成环，所以我们先把环破开，就是环翻倍（n+n），让尾连头。然后求出所有前缀异或和pre
因为要把n分成长度为len的num个区间。
我们要尝试len的每一种情况，让每个区间内的len个数异或和，然后看组成的是不是回文串，找到最大的len情况。
因为我们一开始将2n个数都存了前缀异或和，根据异或的性质，a^a=0,所以我就可以通过前缀异或和轻松算出每个区间的异或值（比如pre[3] ^ pre[6]算出来就是区间[4,6]的异或和，因为3之前的重复就消除了）
求出每区间的异或和放在一个数组b中，再求b是否为回文串。但注意b是一个环直接判断可能不对（比如abb不是回文串，但是abb是一个环如果你用正确的打开方式，它也可以是bab，那就是回文串了），那该怎么办？对，既然是环我们就给它拆成链，我们把项链倍长，如果倍长后的字符串中存在一个子串是回文串且长度超过了倍长前字符串的长度，显然是存在对称轴的。
（还是abb，拆之后就是abbabb,看这个最长回文串的长度（5）是否大于本身（3））
至此基本上就大功告成了
什么？你说用什么求回文串，（那肯定暴力 ）当然用Manacher
b站讲解Manacher
*附码：**

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

int n;
int p[maxn*2];
int str[maxn*2];//数组范围要乘2，因为环要拆成链
int a[maxn*2];
int b[maxn*2];
int pre[maxn*2];

int init(int *s,int len)
{
    str[0]='@';
    int ant=1;
    str[1]='#';
    for(int i=1;i<=len;i++)
    {
        str[++ant]=s[i];
        str[++ant]='#';
    }
    str[++ant]='\0';
    return ant;
}
int manacher(int *s,int num)
{
    int ans=-1;
    int len=init(b,num);
    int mx=0;
    int id=0;
    for(int i=1;i<len;i++)
    {
        if(i<mx)p[i]=min(p[id*2-i],mx-i);
        else p[i]=1;
        while(str[i+p[i]]==str[i-p[i]])p[i]++;
        if(p[i]+i>mx)mx=p[i]+i,id=i;
        ans=max(ans,p[i]-1);
    }
    return ans;
}
bool check(int len) {
    int num = n / len;
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < num; j++) {
            b[j] = pre[(j + 1) * len + i] ^ pre[j * len + i];
        }
        for(int i = 0; i < num; ++i) {
            b[i + num] = b[i];
        }
            if(manacher(b, num * 2)>num)  return true;

    }
    return false;
}
int main() {

    cin>>n;
    for(int i = 1; i <= n; i++) {
        cin>>a[i];
        pre[i] = pre[i-1] ^ a[i];
    }
    for(int i = n + 1; i <= n + n; i++) {
        pre[i] = pre[i - 1] ^ a[i - n];
    }
    int ans = 1;
    for(int i = 1; i <= sqrt(n); i++) {
        if(n % i) continue;
        if(check(n / i)) ans = max(ans, i);
        if(check(i)) ans = max(ans, n / i);
    }
    printf("%d\n", ans);
    return 0;
}