[学习笔记]Manacher

实现

为解决回文串长度奇偶性之间的差距,在相邻两个字符之间和串头串尾插入\('\#'\);
为避免越界,在字符串前加\('\$'\),串尾有\('\setminus0'\).
\(r[i]\)表示以第\(i\)个字符为对称轴的回文串的回文半径,显然现在回文串半径为\(l\)的回文串在原串的回文串长度为\(l-1\).
\(mx\)表示在以\(1\sim\;i-1\)为中心的回文串中,串尾下标的最大值\(+1\);\(id\)表示\(mx\)值所对应的回文串中心.

核心代码:

if(mx>i) r[i]=min(r[(id<<1)-i],mx-i);

\(id\times2-i\)和\(i\)关于\(id\)对称,\(a[id-r[id]+1...id]=a[id...id+r[id]-1]\),所以两者之间取最小值(超出部分匹配不一定成功).
时间复杂度:\(O(n)\).

#define N 200005
using namespace std;
int r[N],m,n,mx,id,ans;
char a[N];
inline int manacher(){
	for(int i=n;i;--i){
		a[i<<1]=a[i];
		a[i<<1|1]='#';
	}
	n=n<<1|1;mx=id=0;
	a[0]='$';a[1]=a[n+1]='#';
	for(int i=1;i<=n;++i){
		r[i]=i<mx?min(r[(id<<1)-i],mx-i):1;
		while(a[i+r[i]]==a[i-r[i]]) ++r[i];
		if(i+r[i]>mx) mx=i+r[i],id=i;
		ans=max(ans,r[i]-1);
	}
	return ans;
}

推荐

http://blog.csdn.net/ggggiqnypgjg/article/details/6645824/

2017-03