M_sea

洛谷4287 [SHOI2011]双倍回文
LuoguBZOJ分析回文的话可以考虑回文自动机$\texttt{manacher}$。显然双倍回文串双倍的快乐的...
扫描右侧二维码阅读全文
16
2019/02

洛谷4287 [SHOI2011]双倍回文

Luogu

BZOJ

分析

回文的话可以考虑回文自动机$\texttt{manacher}$。

显然双倍回文串双倍的快乐的中点是个#

在$MaxRight$更新时,判断所有新出现的回文串的前一半是否为回文串即可。

具体见代码。

代码

//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=2000000+10;

int n,ans=0;
char s[N];
int f[N];

inline void manacher() {
    int mid=0,MaxRight=0;
    for (re int i=1;i<=n;++i) {
        f[i]=(i<MaxRight)?min(f[2*mid-i],MaxRight-i):1;
        while (s[i+f[i]]==s[i-f[i]]) ++f[i];
        if (i+f[i]>MaxRight) {
            if (i&1) {
                for (re int j=max(MaxRight,i+4);j<i+f[i];++j)
                    if (!((j-i)&3)&&f[i-(j-i)/2]>(j-i)/2) ans=max(ans,j-i);
            }
            mid=i,MaxRight=i+f[i];
        }
    }
}

int main() {
    scanf("%d%s",&n,s+1);
    for (re int i=n;i>=1;--i) s[i*2+1]='`',s[i*2]=s[i]; s[1]='`';
    n=n*2+1; manacher();
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 49 PM

2 条评论

  1. wsm000

    你怎么这么熟练啊qwq

    1. M_sea
      @wsm000

      打死

发表评论