about 2 years ago

BZOJ 3676: [Apio2014]回文串

给一个串求回文串 长度×出现次数 的最大值
|S|≤300000.

该出现的早已出现╰( ̄▽ ̄)╭。
统计次数的方式和SAM如出一辙。

参考文献:

有关回文自动机PAM的探讨-PHX
Palindromic Tree——回文树【处理一类回文串问题的强力工具】-poursoul

#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <cstdio>
#include <bitset>
#include <cctype>
#include <cstring>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(x,s,t) for(register int t_=t,x=s;x<t_;x++)
#define per(x,s,t) for(register int s_=s,x=(t)-1;x>=s_;x--)
#define travel(x) for(int I=last[x],to;I&&(to=e[I].to);I=e[I].nxt)
#define prt(x) cout<<#x<<":"<<x<<" "
#define prtn(x) cout<<#x<<":"<<x<<endl
#define y1 asfkagn
#define y2 fansfk
#define rank gkalsfm
#define hash gafgalsf
#define inf (1<<30)
#define INF (1ll<<61)
#define showtime printf("%f",1.0*clock()/CLOCKS_PER_SEC)

typedef long long ll;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;

const long double pi=acos(-1);

template<class T>void sc(T &x)
{
    int f=1;char c;x=0;
    while(c=getchar(),c<48)if(c=='-')f=-1;
    do x=x*10+(c^48);
    while(c=getchar(),c>47);
    x*=f;
}
template<class T>void nt(T x)
{
    if(!x)return;
    nt(x/10);
    putchar('0'+x%10);
}
template<class T>void pt(T x)
{
    if(x<0)x=-x,putchar('-');
    if(!x)putchar('0');
    else nt(x);
}
template<class T>void pts(T x)
{
    pt(x);putchar(' ');
}
template<class T>void ptn(T x)
{
    pt(x);putchar('\n');
}

template<class T>inline void Max(T &x,T y){if(x<y)x=y;}
template<class T>inline void Min(T &x,T y){if(x>y)x=y;}

const int maxn=300010;
ll ans;
char str[maxn];
namespace PAM
{
    int pre[maxn],v[maxn],c[maxn],son[maxn][26],tot,last;
    void Init()
    {
        rep(i,0,tot+1)
        {
            v[i]=c[i]=0;
            memset(son[i],0,sizeof son[i]);
        }
        last=0;tot=1;
        v[1]=-1;pre[0]=1;
    }
    void ins(char ch,int n)
    {
        int x=ch-'a';
        while(str[n]!=str[n-v[last]-1])last=pre[last];
        if(!son[last][x])
        {
            ++tot;
            v[tot]=v[last]+2;
            int k=pre[last];
            while(str[n]!=str[n-v[k]-1])k=pre[k];
            pre[tot]=son[k][x];
            son[last][x]=tot;
        }
        last=son[last][x];
        ++c[last];
    }
}
int Solve()
{
    using namespace PAM;
    per(i,1,tot+1)
    {
        Max(ans,1ll*c[i]*v[i]);
        c[pre[i]]+=c[i];
    }
}
int main()
{
// freopen("pro.in","r",stdin);
//  freopen("chk.out","w",stdout);
 scanf("%s",str+1);
    ans=-1;
    PAM::Init();
    for(int i=1;str[i];i++)PAM::ins(str[i],i);
    Solve();
    ptn(ans);
    return 0;
}
← 后缀自动机试水 一台多串建立的后缀自动机 →