[CERC2019] ABB 题解

题目可以转化为求最长回文子串，答案就是长度减去最长回文子串的长度。看到是求最长回文子串，一眼就容易想到马拉车。

此题只需在求出回文半径的基础上储存回文串的右端点，将求出的右端点排序，只要右端点不在最后的字符就结束（不能补），如果在最后的字符就取原字符串长度与当前回文子串的差值的最小值（需要补的字符个数）。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10,M=8e5+10;
int n;
char a[N],s[M];
int r,c,p[M],vis[M];
int sum,ans=1;
void change(){
	int k=0;
	s[k++]='$',s[k++]='#';
	for(int i=0;i<n;i++)s[k++]=a[i],s[k++]='#';
	s[k++]='&',n=k;
}
int main(){
	cin>>n>>a;
	sum=n;
	change();
	for(int i=1;i<n;i++){
		if(i<r) p[i]=min(p[(c<<1)-i],p[c]+c-i);
		else p[i]=1;
		while(s[i-p[i]]==s[i+p[i]])p[i]++;
		if(p[i]+i>r)r=p[i]+i,c=i;
		if(r==n-1) vis[i]=1;
	}
	for(int i=0;i<n;i++)if(vis[i]==1) ans=max(ans,p[i]);
	cout<<sum-ans+1;
	return 0; 
}