Longest Palindromic Substring

比较容易理解的方法是以s[i]为中心(i=1,…,n)，分回文序列长度为奇数和偶数的情况，向两边扩张，找到最长的回文序列，这样的时间复杂度为O(n^2)。

还有一种很巧妙的Manacher 算法，可以在O(n)时间求字符串的最长回文子串，大致思路如下：

插入特殊字符，使奇数或偶数长度的字符串，长度都变成了奇数，并且在字符串首位加另外一个特殊字符，就不用处理越界问题，如：”12212321”变成”$#1#2#2#1#2#3#2#1#”;这种做法让我想到“求两个有序数组的中位数”的预处理的思想，同样也是为了统一讨论，将数组元素的下标进行处理，对越界的下标赋了特殊值。

用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度。那么p[i]-1正好是原字符串中以s[i]为中心的回文串的长度。

为了计算p[i]，增加变量id,mx，id是当前已知的右边界最大回文串的中心，mx=id+p[id]，即子串的右边界。id,mx初始值都为0。接下来是算法的关键：

当mx>i，p[i]>=MIN(p[2*id-i],mx-i)；当mx<=i，p[i]=1，然后向两边扩展。

对于mx>i的情况，j=2*id-i是i关于id的对称点，利用前面计算的结果，可以得出对称点的两侧回文串的长度。

代码主要部分：

string longestPalindrome(string s) {
	//预处理
	string a = "$#";
	int len = s.size();
	for (int i = 0; i < len; i++)
		a = a + s[i] + "#";

	int p[2002], mx = 0, id = 0;
	memset(p, 0, 2002);
	for (int i = 1; a[i] != 0; ++i)
	{
		p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
		while (a[i + p[i]] == a[i - p[i]])++p[i];
		if (i + p[i] > mx)
		{
			id = i;
			mx = i + p[i];
		}
	}
	int tmp = 0;
	for (int i = 1; i < 2002; i++)
		tmp = p[tmp] > p[i] ? tmp : i;
	return s.substr((tmp-p[tmp] + 1)/2, p[tmp] - 1);
}