LeetCode 5. Longest Palindromic Substring

1. 建立長度為2*s.size()+1的字元串str, 在str奇數位指派為#, 偶數位str[i] = s[i/2] —— 亦即在字元串s的兩邊及相鄰字元間加上#. 

這樣的好處是不用考慮最長回文長度是奇數還是偶數的情況。在str中標明中心，對比兩邊即可：

若最長回文長度為偶數，那麼那個中心将是我們額外插入的某個#;

若為奇數，中心仍為未擴充前的s的最長回文子串中心。

2. 可采用manacher算法 (O(n)求最長回文子串)

代碼：

class Solution 
{
public:
	string longestPalindrome(string s) 
	{
		string str(2*s.size()+1, 0);
		// str
		for (size_t i = 0, j = 0; i < str.size(); ++ i)
		{
			if (i % 2 == 0)
			{
				str[i] = 0;
			} else
			{
				str[i] = s[j ++];
			}
		}	
		// p
		int mx = 0, id, max_length=0, max_id; 
		vector<int> p(2*s.size()+1, 0);
		for (int i = 0; i < str.size(); ++ i)
		{
			p[i] = mx>i? min(p[2*id-i], mx-i): 0;
			for ( ; i-p[i]-1>=0 && i+p[i]+1<str.size() 
				&& str[i-p[i]-1] == str[i+p[i]+1]; ++ p[i]) {}			
			if (i + p[i] > mx)
			{
				mx = i + p[i];
				id = i;
			}
			if (max_length < p[i])
			{
				max_length = p[i];
				max_id = i;
			}
		}

		return s.substr((max_id-p[max_id])/2, p[max_id]);
	}
};