【小白爬Leetcode5】最长回文子串 Longest Palindromic Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Manacher算法 O(n)

Manacher算法可以在O(n) 的时间内求以每个字母为回文中心的最大回文子串的长度，然后再从这里面找出最长的那个回文子串就是答案。

关于算法的详细内容，这个回答写的比LeetCode官方解答要好。
有什么浅显易懂的Manacher Algorithm讲解？ - windliang的回答 - 知乎

简单来说，Manacher算法本质上是一种特殊的动态规划算法，其状态转移方程给出的值不一定是最终答案，但不会高于最终答案。通过状态转移方程得到值要经过普通的中心扩展来测试是否有更优的解答。具体过程分为几个大模块：

1. 预处理。每个字母之间塞一个特殊符号（比如#）进去，这样可以cover单字符回文中心（如：ada）和双字符回文中心的情况（如:adda）的情况。然后再在首、尾处各加一个不同的字符串来控制中心扩展的时候不会溢出，最终转化的效果为：abcde转化为^#a#b#c#d#e#!
2. 设当前的回文中心为C，C的最长回文右边界为R。在求以i为回文中心的最长回文半径P[i]的时候，如果i在以当前回文中心C的回文半径内(即i<R)，则可以利用回文字符串的中心对称性：设i关于C的对称点为i_mirror = C - (i - C) = 2*C - i，那么P[i]保底是P[i] = min(R - i, P[i_mirror])。如果i>=R，以及i_mirror碰到左边界的时候，那么就不能用中心对称性了，老老实实通过中心扩展来求。

class Solution {
public:
	string longestPalindrome(string s) {
		//Manacher Algorithm
		if (s.size() < 2) return s;
		string S = Preprocess(s);
		int n = S.size();
		int C = 0; //回文中心
		int R = 0; //右边界
		vector<int> P(n, 0); //初始化回文半径数组
		for (int i = 1; i < n-1; i++) {
			if (i < R) { //i在右边界内，可以应用回文的对称性
				int i_mirror = C - (i - C); //即2*C-i
				P[i] = min(R - i, P[i_mirror]); //保证P[i]不超过R右边界,才能用对称性
			}

			//中心扩展，因为有对称性cover不了的情况
			while (i - P[i] - 1 >= 0 && i + P[i] + 1 < S.size() && S[i - P[i] - 1] == S[i + P[i] + 1]) {
				P[i]++;
			}
			//判断是否需要更新R和C
			if (P[i] + i > R) {
				C = i;
				R = i + P[i];
			}
		}
		//找最大的P值
		int P_max = 0;
		int C_max = 0;
		for (int i = 1; i < n-1; i++) {
			if (P[i] > P_max) {
				P_max = P[i];
				C_max = i;
			}
		}
		return s.substr((C_max - P[C_max])/2, P[C_max]);
	}
private:
	string Preprocess(const string& s) {
		string ret = "^";
		for (auto c : s) {
			ret += '#';
			ret += c;
		}
		ret += "#$";
		return ret;
	}
};

时间复杂度：O(n)
空间复杂度：O(n)