Manacher Algorithm

string Preprocess(string s) { // 字符串预处理
	string res = "#"; //在每个字符前后添加扩展字符
	for (int i = 0; i < s.size(); i++) {
		res += s[i];
		res += "#";	
	}
	return res;
}

string Manacher(string s) {
	string t = Preprocess(s);
	string ans = "";
	vector<int> p(t.size(), 0);
	int mx = 0;
	for(int i = 0, c = 0, r = 0, len; i < t.size(); i++) {
		// 当 i < r 时,
			// 若此时 i + s[i] 在 r 内， 则 r - i >= p[2 * c - i]
			// len = p[2 * c - i]
			// 若此时 i + s[i] 在 r 外， 则 r - i <= p[2 * c - i]
			// len = r - i
		// 当 i >= r 时
			// 回文字符串即为 i 本身，len = 1
		len = i < r ? min(r - i, p[2 * c - i]) : 1; 
		
		while (i + len < t.size() && i - len >= 0 && t[i + len] == t[i - len]){	// 不管是否可以扩展，都尝试扩展
			len++;
		}
		if (i + len > r){ //更新新的回文中心和回文半径
			r = i + len;
			c = i;
		}
		if(len > mx){ // 维护最长回文子字符串
			mx = len;
			ans = s.substr((i - len + 1)/2, len - 1);
		}
		p[i] = len;
	}
	return ans;
}