回文串(bzoj 3676)

Description

考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出
现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最
大出现值。

Input

输入只有一行，为一个只包含小写字母(a -z)的非空字符串s。

Output

输出一个整数，为逝查回文子串的最大出现值。

Sample Input

【样例输入l】
abacaba

【样例输入2]
www

Sample Output

【样例输出l】
7

【样例输出2]
4

HINT

一个串是回文的，当且仅当它从左到右读和从右到左读完全一样。

在第一个样例中，回文子串有7个：a，b，c，aba，aca，bacab，abacaba，其中：

● a出现4次，其出现值为4：1：1=4

● b出现2次，其出现值为2：1：1=2

● c出现1次，其出现值为l：1：l=l

● aba出现2次，其出现值为2：1：3=6

● aca出现1次，其出现值为1=1：3=3

●bacab出现1次，其出现值为1：1：5=5

● abacaba出现1次，其出现值为1：1：7=7

故最大回文子串出现值为7。

【数据规模与评分】

数据满足1≤字符串长度≤300000。

/*

    调了一个晚上，终于调出来了，二分的时候出了一些差错。

    因为一个长度为n的字符串，本质不同的回文串只有n个，所以这个题很明显需要处理出所有的回文串，然后再查询字符串中它出现的次数。

    提前处理出height数组，然后查询某个字串的时候，找到它的排名，向上向下二分查询次数。

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define N 300100

#define lon long long

using namespace std;

int s[N],t1[N],t2[N],c[N],sa[N],rank[N],height[N],n,m=;

int p[N*],st[N][],lg2[N];

char ch[N],s1[N*];lon ans;

bool cmp(int *y,int a,int b,int k){

    int a1=y[a],b1=y[b];

    int a2=a+k<n?y[a+k]:-;

    int b2=b+k<n?y[b+k]:-;

    return a1==b1&&a2==b2;

}

void DA(){

    int *x=t1,*y=t2;

    for(int i=;i<m;i++) c[i]=;

    for(int i=;i<n;i++) c[x[i]=s[i]]++;

    for(int i=;i<m;i++) c[i]+=c[i-];

    for(int i=n-;~i;i--) sa[--c[x[i]]]=i;

    for(int k=,p=;k<=n;k*=,m=p,p=){

        for(int i=n-k;i<n;i++) y[p++]=i;

        for(int i=;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

        for(int i=;i<m;i++) c[i]=;

        for(int i=;i<n;i++) c[x[y[i]]]++;

        for(int i=;i<m;i++) c[i]+=c[i-];

        for(int i=n-;~i;i--) sa[--c[x[y[i]]]]=y[i];

        swap(x,y);p=;x[sa[]]=;

        for(int i=;i<n;i++)

            if(cmp(y,sa[i-],sa[i],k)) x[sa[i]]=p-;

            else x[sa[i]]=p++;

        if(p>=n) break;

    }

}

void get_ht(){

     for(int i=;i<n;i++) rank[sa[i]]=i;

    for(int i=,j,k=;i<n;height[rank[i++]]=k){

        if(!rank[i]) continue;

        j=sa[rank[i]-];k=k?k-:k;

        while(j+k<n&&i+k<n&&s[i+k]==s[j+k]) k++;

    }

    memset(st,/,sizeof(st));

    for(int i=;i<n;i++) st[i][]=height[i];

    for(int i=;i<=n;i++) lg2[i]=lg2[i>>]+;

    for(int j=;<<j<=n;j++)

        for(int i=;i+(<<j)-<n;i++)

            st[i][j]=min(st[i][j-],st[i+(<<j-)][j-]);

}

int query(int l,int r){

    if(l>r) return ;

    int k=lg2[r-l+];

    return min(st[l][k],st[r-(<<k)+][k]);

}

lon solve(int l,int r){

    l=(l&)?l/:l/-;

    r=(r&)?r/-:r/-;

    if(l==&&r==){

        int aa=;

    }

    int pos=rank[l],L=-,R=pos,tmp1=pos,tmp2=pos;

    while(L<R-){

        int mid=L+R>>;

        if(query(mid+,pos)>=r-l+) R=mid,tmp1=mid;

        else L=mid;

    }

    L=pos;R=n;

    while(L<R-){

        int mid=L+R>>;

        if(query(pos+,mid)>=r-l+) L=mid,tmp2=mid;

        else R=mid;

    }

    return (lon)(tmp2-tmp1+)*(r-l+);

}

void manacher(){

    int len=n*+;

    s1[]='$';s1[len]='#';

    for(int i=;i<n;i++){

        s1[i*+]='#';

        s1[i*+]=ch[i];

    }

    p[]=;int pos=,maxr=;

     for(int i=;i<=len;i++){

        if(i<maxr) p[i]=min(maxr-i,p[pos*-i]);

        else p[i]=;

        while(s1[i+p[i]]==s1[i-p[i]]){

            if(i+p[i]>maxr) ans=max(ans,solve(i-p[i],i+p[i]));

            p[i]++;

        }

        if(i+p[i]>maxr) pos=i,maxr=i+p[i];

    }

}

int main(){

    scanf("%s",ch);n=strlen(ch);

    for(int i=;i<n;i++) s[i]=ch[i]-'a';

    DA();get_ht();

    manacher();

    cout<<ans;

    return ;

}

巴特西