洛谷 P3649 [APIO2014]回文串 / YbtOJ「字符串算法」第3章 后缀自动机 H. 回文匹配 题解--zhengjun

蒟蒻不会 SAM，所以只好用 SA + Manacher + st 表 + set + 单调栈 + 双指针的笨重做法了。

首先处理出每个点为中心的最长回文串长度 o d d i odd_i oddi​，以及以 i i i 和 i + 1 i+1 i+1 为中心左右对称的最长回文串长度 e v n i evn_i evni​，这一步可以用 Manacher 轻松搞定。

接着求出以 i i i 为左端点最长的回文串长度，就是一个区间修改，最后单点查询，可以用线段树或者在 st 表上面打标记之后下推到最底层也可以。

然后再对于原串跑一次 SA，先把出现次数为 1 1 1 的考虑掉，然后考虑出现次数大于 1 1 1 的情况：

就是枚举每个排名为 i ( i > 1 ) i(i>1) i(i>1) 的后缀，用单调栈求出 i i i 左右第一个小于 h e i g h t i height_i heighti​ 的 l , r l,r l,r，所以 ∀ j ∈ [ l + 1 , r − 1 ] forall jin[l+1,r-1] ∀j∈[l+1,r−1]，都有 h e i g h t j ≥ h e i g h t i height_jge height_i heightj​≥heighti​，此时，与 s a i sa_i sai​ 号后缀的公共前缀 ≥ h e i g h t i ge height_i ≥heighti​ 的个数就有 r − l r-l r−l 个，于是问题就转换成了：

求出每个左端点在 i i i，右端点不超过 i + h e i g h t i − 1 i+height_i-1 i+heighti​−1 的最长的回文子串。

这样对于回文串长度分奇偶讨论，下面讨论奇数的，偶数的一样做：

当求左端点在 i i i 时的答案时，设 j = i + h e i g h t i − 1 j=i+height_i-1 j=i+heighti​−1，那么就要找到一个最大的 k k k 满足：

i ≤ k ≤ ⌊ i + j 2 ⌋ , o d d k ≥ k − i + 1 ile kle lfloorfrac{i+j}{2}rfloor,odd_kge k-i+1 i≤k≤⌊2i+j​⌋,oddk​≥k−i+1

转化一下，第二个条件变为 k − o d d k ≤ i − 1 k-odd_kle i-1 k−oddk​≤i−1。

于是我们可以将所有的 k k k 按照 k − o d d k k-odd_k k−oddk​ 升序排序，然后从小到大枚举 i i i，每一次双指针把比 i i i 小的 k − o d d k k-odd_k k−oddk​ 加入集合中，然后只要满足第一个条件即可，也就是在集合中查询区间 [ i , ⌊ i + j 2 ⌋ ] [i,lfloorfrac{i+j}{2}rfloor] [i,⌊2i+j​⌋] 中最大的数，一个 upper_bound 即可。

回文串长度为偶数时同理。

#include
using namespace std;typedef long long ll;const int N=3e5+10,K=log2(N)+2;sets0,s1;char s[N],t[N<<1];
int n,m,rk[N],sa[N],old[N<<1],id[N],p[N],cnt[N],h[N],l[N<<1],r[N],f[K][N],lg[N],stk[N],top,odd[N],evn[N],x0=1,x1=1,cur[2][N];
void getsa(){
	m=128;for(int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for(int i=n;i>=1;i--)sa[cnt[rk[i]]--]=i;for(int i=1;i<=m;i++)cnt[i]=0;for(int len=1,k=0;len==1||m^n;m=k,len<<=1){
		k=0;for(int i=n-len+1;i<=n;i++)p[++k]=i;for(int i=1;i<=n;i++)if(sa[i]>len)p[++k]=sa[i]-len;
		for(int i=1;i<=n;i++)cnt[id[i]=rk[p[i]]]++;for(int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for(int i=n;i>=1;i--)sa[cnt[id[i]]--]=p[i];for(int i=1;i<=n;i++)old[i]=rk[i];for(int i=1;i<=m;i++)cnt[i]=0;
		k=0;for(int i=1;i<=n;i++)rk[sa[i]]=old[sa[i]]==old[sa[i-1]]&&old[sa[i]+len]==old[sa[i-1]+len]?k:++k;
	}for(int i=1,k=0;i<=n;i++){if(k)k--;while(max(sa[rk[i]-1],i)+k<=n&&s[i+k]==s[sa[rk[i]-1]+k])k++;h[rk[i]]=k;}
}
void update(int l,int r,int x){int k=lg[r-l+1];f[k][l]=max(f[k][l],x);f[k][r-(1<for(int i=K-1;i>=1;i--)for(int j=1;j+(1<
	int mx=0;while(x1<=n&&cur[1][x1]-odd[cur[1][x1]]>1);if(it!=s1.begin()){it--;if(*it>=i)mx=(*it-i)<<1|1;}//算长度时小心细节
	it=s0.upper_bound((i+j-1)>>1);if(it!=s0.begin()){it--;if(*it>=i)mx=max(mx,(*it-i+1)<<1);}return mx;
}
int main(){
	scanf("%s",s+1);n=strlen(s+1);m=0;t[m++]='#';for(int i=1;i<=n;i++)t[m++]=s[i],t[m++]='#';for(int i=0,mx=-1,q=-1;i
		l[i]=i>mx?1:min(mx-i+1,l[(q<<1)-i]);while(i-l[i]>=0&&i+l[i]mx)mx=i+l[i]-1,q=i;//马拉车 Manacher
	}for(int i=1,j=1;i>1;for(int i=2,j=1;i>1;
	for(int i=2;i<=n;i++)lg[i]=lg[i>>1]+1;for(int i=1,j=1;i>1)+1,j,j<<1);
	for(int i=2,j=1;i1)update(j-(l[i]>>1)+1,j,j<<1|1);query();getsa();
	stk[0]=1;for(int i=2;i<=n;i++){while(top&&h[i]<=h[stk[top]])top--;l[i]=stk[top];stk[++top]=i;}//单调栈求出左右端点 l,r
	stk[top=0]=n+1;for(int i=n;i>=2;i--){while(top&&h[i]<=h[stk[top]])top--;r[i]=stk[top];stk[++top]=i;}
	ll ans=0;for(int i=1;i<=n;i++)ans=max(ans,f[0][sa[i]]-(sa[i]<<1)+1ll);for(int i=1;i<=n;i++)cur[0][i]=cur[1][i]=i;
	sort(cur[0]+1,cur[0]+n,[](int x,int y){return x-evn[x]return x-odd[x]1)ans=max(ans,ll(r[rk[i]]-l[rk[i]])*get(i,i+h[rk[i]]-1));cout< 
有错误请指出，谢谢–zhengjun