leetcode - 5. Longest Palindromic Substring

manacher算法，比动态规划快一些

class Solution {
public:
	string longestPalindrome(string s) {
		int n = s.size(), m(1), f(1), mm(1), r(1);
		char *p = new char[n * 2 + 4];
		int *a = new int[n * 2 + 4];
		p[0] = '$';
		p[1] = '#';
		p[n * 2 + 2] = 0;
		p[n * 2 + 3] = 0;
		for (int i = 0; i < n; ++i)
		{
			p[2 * i + 3] = '#';
			p[2 * i + 2] = s[i];
		}
		a[0] = a[1] = 1;
		for (int i = 2; i < (2 * n + 3); ++i)
		{
			if (f > i)
			{
				a[i] = min(a[2 * m - i], f - i + 1);
			}
			else {
				a[i] = 1;
			}
			while (p[i + a[i]] == p[i - a[i]])
			{
				++a[i];
			}
			if (a[i] > a[mm])
			{
				mm = i;
			}
			if ((i + a[i] - 1) >= f)
			{
				f = i + a[i] - 1;
				m = i;
			}
		}
		return s.substr((mm - a[mm]) / 2, a[mm] - 1);
	}
};