Leetcode #5

学习了一下Manacher算法，简单来说就是从中心往外扩展，同时利用len数组，根据对称性，省去不必要的扫描，具体做法见https://www.cnblogs.com/mini-coconut/p/9074315.html

class Solution {
public:
	string longestPalindrome(string s)
	{
		string manaStr = "$#";
		for (int i = 0; i < s.size(); i++)	//首先构造出新的字符串
		{
			manaStr += s[i];
			manaStr += '#';
		}
		vector<int> len(manaStr.size(), 0);	//用一个辅助数组来记录最大的回文串长度，注意这里记录的是新串的长度，原串的长度要减去1
		int pos = 0, p = 0;
		int start = 0, maxLen = 0;
		for (int i = 1; i < manaStr.size(); i++)
		{
			len[i] = i < p ? min(len[2 * pos - i], p - i) : 1;
			while (i + len[i] < manaStr.size() && i - len[i] > 0 && manaStr[i + len[i]] == manaStr[i - len[i]])         //这里要注意数组越界的判断，源代码没有注意，release下没有报错
				len[i]++;
			if (i + len[i] > p)				//如果新计算的最右侧端点大于p,则更新pos和p
			{
				pos = i;
				p = i + len[i];
			}
			if (len[i] - 1 > maxLen)
			{
				start = (i - len[i]) / 2;
				maxLen = len[i] - 1;
			}
		}
		return s.substr(start, maxLen);
	}
};