Manacher 算法俗称“马拉车”，是一种线性时间求解最长回文子串的算法。。

算法

引入

任何字符串都可以转为奇数下标匹配问题。

Manacher 算法可以计算出每个字符 s_i 为中心时的回文半径，维护了一个当前最右回文串边界 R 以及其中心 C，表示已有回文串能延伸最远的右边界（LeetCode 中称为“臂长”）。当一个字符位于 (C, C + R) 以内时，意味着可以“偷懒”，快速利用对称点得到当前的回文串。

算法流程

实现

string longestPalindrome(string s) {
	string text = "^?";
	for (int i = 0; i < s.length(); i++)
	{
		text += s[i];
		text += '?';
	}
	text += '$';

	const int n = text.length();
	vector<int> p(n, 0);
	int c = 0, r = 0;
	for (int i = 0; i < n; i++)
	{
		int radius = 1;
		if (i < r)
		{
			radius = min(p[2 * c - i], r - i);
			p[i] = radius;
		}
		else
		{
			p[i] = 0;
		}
		{
		for (; i - radius >= 0 && i + radius < n; radius++)
		{
			if (text[i - radius] == text[i + radius])
			{
				p[i] = radius;
				if (i + radius > r)
				{
					r = i + radius;
					c = i;
				}
			}
			else
			{
				break;
			}
		}
		}
	}
	int l, max_len = 0;
	for (int c = 1; c < n - 1; c++)
	{
		if (p[c] > max_len)
		{
			max_len = p[c];
			l = (c - p[c]) / 2;
		}
	}
	return s.substr(l, max_len);
}