GDKOI2016 Day2 T3 項鍊

T3 項鍊

給出一個環狀字元串，求删除連續一段後剩下的字元為對稱的最大長度、

首先你要知道怎樣的一個字元串算是對稱的。一定是由兩個回文串拼成的。我們可以倍長原串，然後枚舉開頭，這樣删除的一定是枚舉的串的字首。

用manacher預處理出所有的回文中心的擴充半徑。兩個合法的回文中心i和j一定滿足j-i<=n&j-p[j]<=i+p[i]。并且它的串的長度就是j-i。于是我們用線段樹維護一個區間最左邊的i+p[i]比j-p[j]大的位置即可。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 200005
#define inf 0x7fffffff
using namespace std;
int p[*N],t[N*6],n,tot,id,mx,ans,k;
char s[N],ch[*N];
void change(int v,int l,int r,int x,int y) {
    if (l==r) {t[v]=y;return;}
    int m=(l+r)/;
    if (x<=m) change(v*2,l,m,x,y);else change(v*2+,m+,r,x,y);
    t[v]=max(t[v*2],t[v*2+]);
}
void get(int v,int l,int r,int x) {
    if (l==r) {if (t[v]>=x) k=l;return;}
    int m=(l+r)/;
    if (t[v*2]>=x) get(v*2,l,m,x);
    else if (t[v*2+]>=x) get(v*2+,m+,r,x);
}
void find(int v,int l,int r,int x,int y,int z) {
    if (k||x>y) return;
    if (l==x&&r==y) {
        get(v,l,r,z);return;
    }
    int m=(l+r)/;
    if (y<=m) find(v*2,l,m,x,y,z);
    else if (x>m) find(v*2+,m+,r,x,y,z);
    else find(v*2,l,m,x,m,z),find(v*2+,m+,r,m+,y,z);
}
void ext(int x) {
    while (p[x]+x<tot&&x-p[x]>&&ch[p[x]+x+]==ch[x-p[x]-]) p[x]++;
}
int main() {
    scanf("%s",s+);n=strlen(s+);
    fo(i,n+,n*2) s[i]=s[i-n];ch[++tot]='#';
    fo(i,,n*2) ch[++tot]=s[i],ch[++tot]='#';
    fo(i,,tot*3) t[i]=inf;
    fo(i,,tot) {
        if (i>=mx) ext(i);else {
            int j=id*2-i;
            if (p[j]<mx-i) p[i]=p[j];else 
            p[i]=mx-i,ext(i);
        }
        if (p[i]+i>mx) mx=p[i]+i,id=i;
        k=;find(,,tot,max(,i-n),i-,i-p[i]);
        if (k) ans=max(ans,i-k);
        change(,,tot,i,i+p[i]);
    }
    printf("%d",ans);
}