ABB

题意：

长度为n的字符串，问最少添加多少字符可以使其构成回文字符串

题解：

最长回文字符串我的第一反应是manacher马拉车算法，那我们直接马拉车找到已有最长回文串，然后总长度减去不就是答案吗？非也 ~ ~ 。注意是让我们构造最长回文字符串，我们会发现，如果我们用马拉车找到的最长回文串的最右端不是字符串最右端，那此情况就相当于作废
比如：
murderforajarofz
我们可以找到最长回文串forajarof，但是最后一位z并不在里面，那你无论怎么构造也用不到forajarof这个回文串，也就是我们要找最长的带最后一个字符的回文字符串
我们直接在manacher的基础上改就可以，原本式子中的ans，我们每查找完一次清零，也就是如果找到的回文串不是带尾的不要，如果带尾保留最大值
详细看代码

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 9*1e5+4;
char s[maxn];
char str[maxn];
int p[maxn];//表示以i为中心的最长回文子串长度，

int init() {
   
    int len = strlen(s);
    str[0] = '@', str[1] = '#';
    int j = 2;
    for (int i = 0; i < len; ++i) str[j++] = s[i], str[j++] = '#';
    str[j] = '\0';
// cout<<j<<endl;
    return j;
}
int manacher() {
   
   
	int len = init(),sum=-1; 
	int mx = 0;//同时记录一个当前延伸最远的回文子串 
	int id = 0;//对称中心 
	int ans = -1;
    for (int i = 1; i < len; ++i) {
   
    	
        if (i < mx) p[i] = min(p[id * 2 - i], mx - i);
        else p[i] = 1;
        while (str[i + p[i]] == str[i - p[i]]) p[i]++;
        //if(i+p[i]==len-1) 
        if (p[i] + i > mx) mx = p[i] + i, id = i;
     // cout<<"id="<<id<<endl;
    	ans = max(ans, p[i] - 1);
		if(mx==len)sum=max(sum,ans);
		
		//cout<<"ans="<<ans<<endl;
    	//cout<<"mx="<<mx<<endl;
    	//cout<<"sum="<<sum<<endl;
 		ans=0;
	}
	return sum;
}
int main() 
{
   
	int t;
	cin>>t;
	for(int i=0;i<t;i++)cin>>s[i];
	if(manacher()==0)
	cout<<t-1<<endl;
	else 
  	cout <<t-manacher()<<endl;
    return 0;
}