首页 > 代码库 > [bzoj]

[bzoj]

 

技术分享
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=300010;
char s[maxn];
int l,len,sz;
long long ans;
struct trees{int fail,len,t[27],num,defail;}t[maxn];
int getfail(int x)
{
    while(s[len-t[x].len-1]!=s[len])x=t[x].fail;
    return x;
}
void insert()
{
    int x=s[++len]-a;
    l=getfail(l);
    if(!t[l].t[x])
    {
        sz++;t[sz].num=1;
        t[sz].len=t[l].len+2;
        ans=max(ans,1ll*t[sz].len);
        int g=getfail(t[l].fail);
        t[sz].fail=t[g].t[x];
        t[t[g].t[x]].defail=sz;
        t[l].t[x]=sz;
    }
    else
    {
        t[t[l].t[x]].num++;
        ans=max(ans,1ll*t[t[l].t[x]].num*t[t[l].t[x]].len);
    }
    l=t[l].t[x];
}
int main()
{
    scanf("%s",s+1);
    s[0]=-1;sz=1;
    t[0].fail=t[1].fail=1;
    t[1].defail=0;
    t[0].len=0;t[1].len=-1;
    t[0].num=t[1].num=0;
    l=len=0;
    int n=strlen(s+1);
    ans=0;
    for(int i=1;i<=n;i++)insert();
    printf("%lld",ans);
    return 0;
}
View Code

 

[bzoj]