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

本文主要是介绍P4555 [国家集训队] 最长双回文串题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

补一个题解区没有的解法。

解法

通过哈希实现的线性做法，受讨论区启发。

考虑枚举双回文串的分割点，即分割点左右各是一个回文串，对于每个分割点，我们最大化两个回文串的长度，而且两个回文串是互不影响的。

问题转化为求原串的所有前缀的最长回文后缀和所有后缀的最长回文前缀。因为两个问题求法是类似的，所以这里只说如何求所有前缀的最长回文后缀。

我们记 $pre_i$ 表示前 $i$ 个字符组成的最长回文后缀。显然， $pre_i \le i$ 。再思考一下，可以发现 $pre_i \le pre_{i-1}+2$ ，因为回文中心不可能向左移动，否则 $pre_{i-1}$ 将会变得更大，不符合定义。我们可以从 $min(i,pre_{i-1}+2)$ 开始向 $1$ 暴力枚举 $pre_i$ ，使用哈希 $\mathcal{O}(1)$ 检验。

乍一看，这个做法是暴力，不能保证复杂度。但发现每次 $p re$ 的上界只能增加 $2$ ，一共只能增加 $2 n$ ，所以只会暴力检验 $\mathcal{O}(n)$ 次，所以总复杂度是线性。

代码

#include<bits/stdc++.h>
namespace fast_IO
{#define Getchar() p1==p2 and (p2=(p1=Inf)+fread(Inf,1,1<<21,stdin),p1==p2)?EOF:*p1++char Inf[1<<21],*p1,*p2;inline bool inrange(const char &ch){if(ch>=33 && ch<=126) return true;return false;}inline void read(std::string &st,char c=Getchar()){st.clear();while(!inrange(c)) c=Getchar();while(inrange(c)) st+=c,c=Getchar();}
};
using namespace fast_IO;
#define int long long
std::string st;
int pre[100010],suf[100010],n,has1[100010],has2[100010],pw[100010],ans;
const int base=131,p=998244353;
inline int cal1(const int l,const int r)
{if(l>r) return 0;return (has1[r]-has1[l-1]*pw[r-l+1]%p+p)%p;
}
inline int cal2(const int l,const int r)
{if(l>r) return 0;return (has2[l]-has2[r+1]*pw[r-l+1]%p+p)%p;
}
inline void solve()
{pre[1]=1;for(int i=2,len;i<=n;i++){len=std::min(i,pre[i-1]+2);while(cal1(i-len+1,i)!=cal2(i-len+1,i)) len--;pre[i]=len;}suf[n]=1;for(int i=n-1,len;i;i--){len=std::min(n-i+1,suf[i+1]+2);while(cal1(i,i+len-1)!=cal2(i,i+len-1)) len--;suf[i]=len;}
}
signed main()
{read(st),n=st.size(),st="#"+st,pw[0]=1;for(int i=1;i<=100000;i++) pw[i]=pw[i-1]*base%p;for(int i=1;i<=n;i++) has1[i]=(has1[i-1]*base+st[i]-'a'+1)%p;for(int i=n;i;i--) has2[i]=(has2[i+1]*base+st[i]-'a'+1)%p;solve();for(int i=1;i<n;i++) ans=std::max(ans,pre[i]+suf[i+1]);std::cout<<ans;return 0;
}