洛谷4555 [国家集训队]最长双回文串

Luogu

BZOJ

分析

$\mathrm{manacher}$ 。

处理出两个数组 $L[i]$ 和 $R[i]$ ,分别表示以 $i$ 为开头/结尾的最长回文串长度。

显然可以在跑完 $\mathrm{manacher}$ 后 $O(n)$ 得出。

然后直接扫一遍求出 $\max\{L[i]+R[i]\}$ 就行了。

需要注意的是,这里的 $L[i]$ 和 $R[i]$ 都不能为 $0$

否则你会在这组数据上 $\mathrm{WA}$ :aba

具体实现及细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

int n;
char a[N],s[N];
int f[N];
int L[N],R[N];

inline void manacher(int n) {
    int mr=1,mid;
    for (re int i=1;i<=n;++i) {
        if (i<mr) f[i]=min(f[2*mid-i],mr-i);
        else f[i]=1;
        while (i-f[i]>=1&&i+f[i]<=n&&s[i-f[i]]==s[i+f[i]]) ++f[i];
        if (i+f[i]>mr) mr=i+f[i],mid=i;
    }
}

int main() {
    scanf("%s",a+1); int n=strlen(a+1);
    
    s[1]='$';
    for (re int i=1;i<=n;++i) s[i*2]=a[i],s[i*2+1]='$';
    n=n*2+2,s[n]='\0';
    manacher(n);
    
    for (re int i=1;i<=n;++i) R[i+f[i]-1]=max(R[i+f[i]-1],f[i]-1);
    for (re int i=1;i<=n;++i) L[i-f[i]+1]=max(L[i-f[i]+1],f[i]-1);
    for (re int i=n;i>=1;i-=2) R[i]=max(R[i],R[i+2]-2);
    for (re int i=1;i<=n;i+=2) L[i]=max(L[i],L[i-2]-2);
    int ans=0;
    for (re int i=1;i<=n;i+=2)
        if (L[i]&&R[i]) ans=max(ans,L[i]+R[i]);
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 12 : 57 PM

5 条评论

  1. Karry5307

    orz 字符串神仙

    我连manacher都不会,只会回文树qwq

    1. smy
      @Karry5307

      回文树聚聚%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

    2. M_sea
      @Karry5307

      您怎么回文树都会啊,您怎么什么都会啊,您怎么这么强啊

      1. Karry5307
        @M_sea

        我怎么这么菜啊

    3. Karry5307
      @Karry5307

      而且还是刚刚学的

发表评论 取消回复