BZOJ 2342 [Shoi2011]双倍回文（Manacher）

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2342

题意：求最长子串使得它有四个相同的回文串SSSS相连组成。

首先跑一边Manacher，初始化出以每一个点为最长回文串的左端点，然后按左端点排序。

枚举中间点$x$，然后找右面的中间点$y$，使得$y$满足

$y-p_yleq x$ 

$yleq x+r_xdiv 2$

用set维护y，然后求出最接近$x+r_xdiv 2$，用--upper_bound()返回$y$的迭代器it。(注意不要直接用lower_bound()

则$ans=max((*it)-i) imes 2$   -->因为有‘#’，*2即可。

AC代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
using namespace std;
const int N=500050;
int p[N*2];
char str[N],s[N*2];
int n,t,ans;
set<int> Set;
set<int>::iterator it;

struct node{
    int v,id;
}a[N];

bool cmp(node x,node y){
    return x.v<y.v;
}

void manacher(int len){
    s[0]='$'; s[++t]='#';
    for(int i=1;i<=len;i++){
        s[++t]=str[i];
        s[++t]='#';
    }
    int pos=0,mx=0;
    for(int i=1;i<=t;i++){
        if(i>mx) p[i]=1;
        else p[i]=min(p[2*pos-i],mx-i);
        while(i+p[i]<=t&&i-p[i]>=1&&s[i+p[i]]==s[i-p[i]]) p[i]++;
        if(i+p[i]>mx){
            mx=i+p[i];
            pos=i;
        }
    }
}

void solve(){
    int q=0;
    for(int i=1;i<=t;i++) if(i&1) a[++q].v=i-p[i],a[q].id=i;
    sort(a+1,a+q+1,cmp);
    int now=1;
    for(int i=1;i<=t;i++) if(i&1){
        while(now<q&&a[now].v<=i) Set.insert(a[now].id),now++;
        it=--Set.upper_bound(i+p[i]/2);
        if(it!=Set.begin()) ans=max(ans,(*it)-i);
    }
    printf("%d
",ans*2);
}

int main(){
    scanf("%d",&n);
    scanf("%s",str+1);
    manacher(n);
    solve();
    return 0;
}