【APIO2014】Palindromes

#103. 【APIO2014】Palindromes

统计

给你一个由小写拉丁字母组成的字符串

对于给你的这个字符串

输入格式

一行，一个由小写拉丁字母（a~z）组成的非空字符串

输出格式

输出一个整数，表示所有回文子串中的最大存在值。

样例一

input

abacaba

output

explanation

用

一个字符串

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中，有

所以回文子串中最大的存在值为

样例二

input

www

output

限制与约定

第一个子任务共 8 分，满足

第二个子任务共 15 分，满足

第三个子任务共 24 分，满足

第四个子任务共 26 分，满足

第五个子任务共 27 分，满足

时间限制：

空间限制：

下载

样例数据下载

思路：

1、manacher找出回文串

2、suffix数组向上向下二分找出串t出现次数

3、用RMQ加速

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=3e5+5;
typedef long long ll;
int n,p[N<<2],f[N][21],log2[N];
char s[N],S[N<<1];
int c[N],h[N],sa[N],tsa[N],rank[N],trank[N];
ll ans;
void DA(int maxx=256){
    int p;
    for(int i=1;i<=maxx;i++) c[i]=0;
    for(int i=1;i<=n;i++) c[rank[i]=s[i]]++;
    for(int i=1;i<=maxx;i++) c[i]+=c[i-1];
    for(int i=n;i;i--) sa[c[rank[i]]--]=i;
    trank[sa[1]]=p=1;
    for(int i=2;i<=n;i++){
        if(rank[sa[i]]!=rank[sa[i-1]]) p++;
        trank[sa[i]]=p;
    }
    for(int i=1;i<=n;i++) rank[i]=trank[i];
    for(int k=1;p<n;k<<=1,maxx=p){
        p=0;
        for(int i=n-k+1;i<=n;i++) tsa[++p]=i;
        for(int i=1;i<=n;i++) if(sa[i]>k) tsa[++p]=sa[i]-k;
        for(int i=1;i<=maxx;i++) c[i]=0;
        for(int i=1;i<=n;i++) trank[i]=rank[tsa[i]];
        for(int i=1;i<=n;i++) c[trank[i]]++;
        for(int i=1;i<=maxx;i++) c[i]+=c[i-1];
        for(int i=n;i;i--) sa[c[trank[i]]--]=tsa[i];
        trank[sa[1]]=p=1;
        for(int i=2;i<=n;i++){
            if(rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+k]!=rank[sa[i-1]+k]) p++;
            trank[sa[i]]=p;
        }
        for(int i=1;i<=n;i++) rank[i]=trank[i];
    }
    for(int i=1,k=0;i<=n;i++){
        int j=sa[rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        h[rank[i]]=k;if(k>0) k--;
    }
}
void RMQ(){
    for(int i=1;i<=n;i++) f[i][0]=h[i];
    for(int i=2;i<=n;i++) log2[i]=log2[i>>1]+1;
    for(int j=1;j<=log2[n];j++){
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);
        }
    }
}
int query(int l,int r){
    if(l>r) return 0;//WA*1
    int k=log2[r-l+1];
    return min(f[l][k],f[r-(1<<k)+1][k]);
}
ll solve(int l,int r){
    if(l>r) return 0;//WA*1
    int pos=rank[l],L=0,R=pos,up=pos,dn=pos;
    while(L+1<R){//WA*1
        int mid=L+R>>1;
        if(query(mid+1,pos)>=r-l+1) R=mid,up=mid;
        else L=mid;
    }
    L=pos,R=n+1;//WA*1
    while(L+1<R){
        int mid=L+R>>1;
        if(query(pos+1,mid)>=r-l+1) L=mid,dn=mid;
        else R=mid;
    }
    return 1LL*(dn-up+1)*(r-l+1);
}
int opl,opr,lal=-1,rar=-1;
void find(char c,int pos,int d){//WA*1
    bool f=0;
    if(c!='#') pos++;else f=1;
    pos/=2;d/=2;
    opr=pos+d;
    pos-=d;
    if(f) pos++;
    opl=pos;
}
void manacher(){
    int l=-1;
    for(int i=1;i<=n;i++) S[++l]='#',S[++l]=s[i];
    S[++l]='#';
    int id=0,mx=-1;ll t;
    for(int i=1;i<l;i++){
        if(id+mx>i) p[i]=min(p[id*2-i],id+mx-i);
        while(i-p[i]-1>=0&&i+p[i]+1<=l&&S[i-p[i]-1]==S[i+p[i]+1]){
            p[i]++;
            if(id+mx<i+p[i]){
                find(S[i],i,p[i]);
                if(opl==lal&&opr==rar) continue;
                lal=opl;rar=opr;//TLE*1
                t=solve(opl,opr);
                if(ans<t) ans=t;
            }             
        }
        if(id+mx<i+p[i]) id=i,mx=p[i];
    }
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    DA();RMQ();//WA*1
    manacher();
    cout<<ans;
    return 0;
}