题解：P10915 [蓝桥杯 2024 国 B] 最长回文前后缀

字符串哈希 + 二分 + 贪心

第一步贪心：考虑到可以删去某一段子串，且对于一段长度

k

，若满足

s_{1 \sim k} = s_{n-k+1 \sim n}

，即初始时前后缀已经存在一个长度为

k

的回文前后缀，那么这一段保留一定不会更劣。这个过程可以用双指针维护。注意特判当不存在满足

k \in [1,n],s_k \ne s_{n-k+1}

的

k

时直接输出

\left \lfloor \dfrac{n}{2} \right \rfloor

，因为要避免相交。

那么问题就转化为在

s_{k+1 \sim n-k}

这一段中删去某个子串，使得这部分删除某个子串后的前后缀更大，然后将这个答案与一开始的

k

加起来即总长度。

第二步贪心：令

s^\prime =s_{k+1 \sim n-k}

，且记

|s^\prime|

为

cnt

，那么对于

s^\prime

这部分怎么删除子串更优呢？考虑贪心策略，不难发现因为

s^\prime_{1} \ne s^\prime_{cnt}

，因此删除中间某部分肯定不优，因为首尾已经不匹配，中间删了等于白删。所以显然最优的策略应该是删除一段前缀或后缀。

那么可以分类讨论，先讨论删除前缀的情况，再讨论删除后缀的情况，最后取最大值。

以删除前缀时为例，删除后缀同理：

考虑枚举删除前缀的长度

i

，则我们需要求

s^\prime _{i+1 \sim cnt}

这段中的最长公共前后缀长度，如何快速求解最长公共前后缀长度？经典套路了，考虑字符串哈希 + 二分快速求解即可。对最长公共前后缀长度进行二分答案，单调性显然是满足的。

假设当前二分的长度为

len

，为了避免当前判定的前缀串与后缀串出现相交的情况，即要满足

i+1+(len-1) \lt cnt-(len-1)

，移项得

2 \times len \lt cnt-i+1

，即

2 \times len \le cnt-i

，即

len \le \left \lfloor \dfrac{cnt-i}{2} \right \rfloor

，因此二分长度的左右边界为

l=0,r=\left \lfloor \dfrac{cnt-i}{2} \right \rfloor

。

代码如下：

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef unsigned long long ULL;
const int N=5e5+5,P=13331;
int n;
char tmp[N],s[N],t[N];
ULL hs[N],ht[N],p[N];
void calc(ULL h[],char *s){
	p[0]=1;
	int len=strlen(s+1);
	rep(i,1,len){
		h[i]=h[i-1]*P+s[i];
		p[i]=p[i-1]*P;
	}
}
ULL getstr(ULL h[],int l,int r){
	return h[r]-h[l-1]*p[r-l+1];
}
void solve(){
	scanf("%s",tmp+1);
	int n=strlen(tmp+1);
	int L=1,R=n;
	while(tmp[L]==tmp[R] && L<=R) L++,R--;
	if(L>R) return cout<<n/2,void();
	int cnt=0;
	rep(i,L,R) s[++cnt]=tmp[i];
	rep(i,1,cnt) t[i]=s[i];
	reverse(t+1,t+1+cnt);
	calc(hs,s);
	calc(ht,t);
	int ans=0;
	rep(i,1,cnt-1){ // 删除前缀
		int l=0,r=(cnt-i)/2;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(getstr(hs,i+1,i+mid)==getstr(ht,1,mid)) l=mid;
			else r=mid-1;
		}
		ans=max(ans,l);
	}
	rep(i,1,cnt-1){ // 删除后缀
		int l=0,r=(cnt-i)/2;
		while(l<r){
			int mid=(l+r+1)>>1;
			if(getstr(ht,i+1,i+mid)==getstr(hs,1,mid)) l=mid;
			else r=mid-1;
		}
		ans=max(ans,l);
	}
	cout<<ans+(L-1);
}

题解：P10915 [蓝桥杯 2024 国 B] 最长回文前后缀

文章操作

字符串哈希 + 二分 + 贪心

相关推荐

评论

题解：P10915 [蓝桥杯 2024 国 B] 最长回文前后缀