题解 | #小易爱回文#

manacher

从前往后找对称中心，计算扩展长度知道该中心包含最后一个字符

再根据对称性，计算出前面需要反转后添加的长度

```cpp
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>


using namespace std;





int main(){
	
	
	string str;
	cin >> str;
	
	string mstr;
	mstr += '$';
	
	for(int i = 0;i < str.size();++i){
		mstr += '#';
		mstr += str[i]; 
	}
	
	mstr += '#';
	mstr += '?';
	
	int p[2000*2 + 10];
	
	int c = 0;
	int mRb = 0;
	p[0] = 0;
	
	
	for(int i = 0;i < mstr.size();++i){
		int lp = 2 * c - i;
		p[i] = min(p[lp], mRb - i);
		
		while(mstr[i - p[i]] == mstr[i + p[i]])
			p[i]++;
			
		if(p[i] + i > mRb){
			mRb = p[i] + i;
			c = i;
		}
			
	}
	
	int pos = mstr.size();
	for(int i = 0;i < mstr.size();++i){
		if(i + p[i] == mstr.size() - 1){
			
			int tmp = i - p[i];
			
			pos = tmp/2;
			break;
		}
	}
	
	
	
	
	//printf("%d\n", pos);
	string appstr = str.substr(0, pos);
	reverse(appstr.begin(), appstr.end());
	 
	str += appstr; 
	
	cout << str;
	return 0;
}