manacher+set

好像这种求回文串形态的都是用manacher，然后求出中心之间奇怪的关系

我们先跑出来manacher，由于只要偶数回文串，我们就只把#位置记录下来，重新保存，然后我们考虑什么情况下区间[x+1,y]*4可以更新答案，x是整个回文串的中心。那么很明显有x+f[x]/2>=y,y-p[y]>=x

碰见这种情况，我们一般先保证一个不等式恒成立，另一个用数据结构搞一搞，那么我们让y-p[y]>=x恒成立，先对y排个序，然后将满足条件的y逐渐加入，插入set，我们枚举的是x，自然希望y越大越好，那么我们在set里查x+f[x]/2的前继，看能是否更新答案。

#include
      
       using namespace std;const int N = 500010;int n, len, ans, pos, mx;char t[N], s[N << 1];int p[N << 1], f[N], y[N];set
       
         S;bool cmp(int i, int j) { return i - f[i] < j - f[j]; }int main(){    scanf("%d%s", &n, t + 1);    s[0] = '!';    s[len = 1] = '#';    for(int i = 1; i <= n; ++i) s[++len] = t[i], s[++len] = '#';     for(int i = 1; i <= len; ++i)     {        if(i < mx) p[i] = min(mx - i, p[2 * pos - i]); else p[i] = 1;        while(s[i - p[i]] == s[i + p[i]]) ++p[i];        if(i + p[i] > mx)        {            pos = i;            mx = i + p[i];        }    }    for(int i = 1; i <= n; ++i) f[i] = (p[i << 1 | 1] - 1) >> 1, y[i] = i;    sort(y + 1, y + n + 1, cmp);    int j = 0;    for(int i = 1; i <= n; ++i)    {        while(y[j + 1] - f[y[j + 1]] <= i && j < n) ++j, S.insert(y[j]);        set
        
          :: iterator it = S.upper_bound(i + (f[i] >> 1));        if(it == S.begin()) continue;        else --it;        if(i + (f[i] >> 1) >= *it && *it - f[*it] <= i) ans = max(ans, (*it - i) * 4);    }    printf("%d\n", ans);    return 0;}