正题

题目链接:https://www.luogu.com.cn/problem/P3649

题目大意

一个字符串，求最大的回文串长度×出现次数

解题思路

构建出\(\text{PAM}\)然后统计一下每个节点作为后缀的次数，\(fail\)树上上传一下信息就好了，时间复杂度\(O(n)\)。

当然也可以\(\text{SAM}+\text{Manacher}+\)倍增，因为一个字符串里本质不同的回文串就是会让马拉车的\(maxright\)增加的回文串，这些最多只有\(n\)个，马拉车跑出来的丢到\(\text{SAM}\)倍增找到对应节点即可。时间复杂度\(O(n\log n)\)

这里写的是\(\text{PAM}\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=3e5+10;

int n,tot,fail[N],len[N],cnt[N],ch[N][26];

char s[N];long long ans;

int get_fail(int x,int n){

    for(;s[n-len[x]-1]!=s[n];)x=fail[x];

    return x;

}

int Insert(int n,int x){

    x=get_fail(x,n);

    int c=s[n]-'a';

    if(!ch[x][c]){

        len[++tot]=len[x]+2;

        int y=get_fail(fail[x],n);

        fail[tot]=ch[y][c];

        ch[x][c]=tot;

    }

    cnt[ch[x][c]]++;

    return ch[x][c];

}

int main()

{

    scanf("%s",s+1);n=strlen(s+1);

    int last=0;len[1]=-1;fail[0]=tot=1;

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

        last=Insert(i,last);

    for(int i=tot;i>=1;i--)

        cnt[fail[i]]+=cnt[i];

    for(int i=1;i<=tot;i++)

        ans=max(ans,1ll*len[i]*cnt[i]);

    printf("%lld\n",ans);

}

巴特西

P3649-[APIO2014]回文串【PAM】

正题

题目大意

解题思路

code

最新文章

热门文章