[ Manacher's algorithm ] Linear time Longest palindromic substring 線性最長回文子串

Manacher演算法是Z algorithm的變種，可以說是雙向的Z algorithm，複雜度也是$\ord N$
其Z function定義如下:
     Z(i)=以位置i為中心的最長回文半徑
但是這樣只能處理回文長度是奇數的子串，因此必須幫字串做一些修改

假設原來的字串是: "asdsasdsa"
修改後變成: "@#a#s#d#s#a#s#d#s#a#"
其中'@'及'#'為不同字元且皆未在原字串中出現過
其Z function陣列為: 0 1 2 1 2 1 6 1 2 1 10 1 2 1 6 1 2 1 2 1
則 最大的數字-1 (10-1=9)就是我們要的答案

這裡提供Manacher algorithm產生Z function陣列的實作:

	/*
	原字串: asdsasdsa
	先把字串變成這樣: @#a#s#d#s#a#s#d#s#a#
	*/
	inline void manacher(char *s,int len,int *z){
	int l=0,r=0;
	for(int i=1;i<len;++i){
	z[i]=r>i?min(z[2*l-i],r-i):1;
	while(s[i+z[i]]==s[i-z[i]])++z[i];
	if(z[i]+i>r)r=z[i]+i,l=i;
	}
	}

view raw Manacher.cpp hosted with ❤ by GitHub