Manacher 马拉车

Manacher 马拉车，一种为了求字符串中最长的回文字串的算法。

这个算法是从暴力的方法转化过来的，暴力肯定是枚举字符串每个字符作为中心，然后向外扩展，这样的复杂度为 \(O(n^2)\)。

而 Manacher 则是按照回文对称的性质的进行优化的，首先回文串有奇数串 \(aba\) 和偶数串 \(abba\) 如果直接对原串进行操作会有些复杂，所以可以将每个字符之间用 # 隔开，当然开头结尾也用 #，这样这个字符串就必定变为一个长度为奇数的字符串，这样就好进行操作。

void change(){
	a[0]=a[1]='#';
	for(int i=0;i<n;i++){
		a[i*2+2]=a[i];
		a[i*2+3]='#';
	}
	n=n*2+2;
	s[n]='#';
}

下一步