洛谷 P4555 [国家集训队]最长双回文串（Manacher）

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

首先明白两个回文串，那么要使两个回文串成立，那么我们只能把$'#'$作为中间节点。

然后我们跑一边Manacher，记录$l[]，r[]$，$l[i]$表示以$i$开头的最长回文串长度，$r[i]$表示以$i$结尾的最长回文串长度。

那么到最后我们只需要用线性的时间来枚举$i$，找$l_i+r_i$最大即可。

但是，在Manacher算法中有局限性：就是我们处理出来的$l，r$都是饱和回文串的，那么我们就要处理不饱和回文串：

$l[i]=max(l[i],l[i-2]-2)$

$r[i]=max(r[i],r[i+2]-2)$

解释一下$1$式，$2$式类似：

其实都是一个递推的过程，l[i-2]即为上一个$‘#’$的位置，$-2$是因为回文串的对称性。

AC代码：

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 const int N=;

 int p[N*],l[N*],r[N*];

 char s[N*],str[N];

 int ans,t;

 void manacher(int len){

     s[]='$'; s[++t]='#';

     for(int i=;i<=len;i++){

         s[++t]=str[i];

         s[++t]='#';

     }

     int pos=,mx=;

     for(int i=;i<=t;i++){

         if(i>mx) p[i]=;

         else p[i]=min(p[*pos-i],mx-i);

         while(i+p[i]<=t&&i-p[i]>=&&s[i-p[i]]==s[i+p[i]]) p[i]++;

         if(i+p[i]>mx){

             mx=i+p[i];

             pos=i;

         }

         l[i-p[i]+]=max(l[i-p[i]+],p[i]-);

         r[i+p[i]-]=max(r[i+p[i]-],p[i]-);

     }

 }

 int main(){

     scanf("%s",str+);

     manacher(strlen(str+));

     for(int i=;i<=t;i+=) l[i]=max(l[i],l[i-]-);

     for(int i=t;i>=;i-=) r[i]=max(r[i],r[i+]-);

     for(int i=;i<=t;i+=) if(l[i]&&r[i]) ans=max(ans,l[i]+r[i]);

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

     return ;

 }

AC代码

巴特西

洛谷 P4555 [国家集训队]最长双回文串（Manacher）

最新文章

热门文章