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

Posted on | In

学长讲过的$Manacher$例题，上课睡觉没听懂

开题的时候毫无思路，最后终于找到思路了

思路主要是枚举分界点，把这个点两边的最长回文串的长度拼起来

在每一次$Manacher$操作完成之后，我们可以顺便维护

  • 以这个回文串的左端点为其左端点的最长回文串的长度

  • 以这个回文串的右端点为其右端点的最长回文串的长度

事实上，这两个最长回文串的长度一定不小于这个回文串的长度

这样我们就可以在线性的时间复杂度里预处理出每个点左右的最长回文串的长度

预处理之后还要递推，大致就是不断地将之前回文串的长度$-$$2$取最大值

最后枚举每个#所在位置，不断更新$ans$取最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<bits/stdc++.h>
using namespace std;
char s[222222];
char t[222222];
int p[222222];
int l[222222];
int r[222222];
int n,k,o,ans;
int main()
{
    scanf("%s",t+1);n=strlen(t+1);
    for(register int i=1;i<=n;++i) s[i*2]=t[i],s[i*2+1]='#';
    s[0]=s[1]='#';n=n*2+2;s[n]='\0';
    for(register int i=0;i<n;++i)
    {
        p[i]=i<o?min(o-i,p[k*2-i]):1;
        while(s[i+p[i]]==s[i-p[i]]) ++p[i];
        if(i+p[i]>o) k=i,o=i+p[i];
        l[i+p[i]-1]=max(p[i]-1,l[i+p[i]-1]);
        r[i-p[i]+1]=max(p[i]-1,r[i-p[i]+1]); 
    }
    for(register int i=n-3;i>0;i-=2) l[i]=max(l[i],l[i+2]-2);
    for(register int i=3;i<n;i+=2) r[i]=max(r[i],r[i-2]-2);
    for(register 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;
}