Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.Example 2:
Input: "cbbd"
Output: "bb"用的 Manacher 算法，如果对注释不太明白可以搜网上的图解。。
class Solution
{
public:
string longestPalindrome(string s)
{
// 马拉车算法
if (s.empty())
return "";
// 先处理一下字符串，给每个字符之间加入#，来解决对称位置的奇偶问题
// 保证所有的串和回文串都是奇数长度
string prep = "#";
for (auto ch : s)
{
prep += ch;
prep += "#";
}
const int size_p = prep.size();
// dp(i) 表示以 i 为中心的最长回文的半径
vector<int> dp(size_p, 0);
// bCur 是以 center 为中心，最长回文的右边界
int center = 0, bCur = 0;
for (int i = 0; i < size_p; i++)
{
// 遍历是从左至右，所以
// center一定小于等于i
// 到i的时候，dp[mirror]是最长回文半径
// mirror 是以 center 为中心，i的对称点
int mirror = center - (i - center);
// 这里分三种情况：
// 1. dp[mirror] > bCur - i,那么 dp[i] = bCur - i，否则的话以 center 为中心，到 bCur 的长度就不是最长回文半径了，与假设不符
// 2. dp[mirror] < bCur - i,那么 dp[i] = dp[mirror],根据 i 和 mirror 是以 center 为中心对称，且 dp[mirror] 在 center 为中心的回文之内，如果 dp[i] 比 dp[mirror] 更大的话，那么与 dp[mirror] 是最大回文前置条件不符
// 3. dp[mirror] == bCur - i，那么 i 的最长回文至少是包含 mirror 的，即 dp[i] >= dp[mirror]，所以还需要后面继续扩展 i 的回文长度的处理。
dp[i] = bCur <= i ? 0 : min(bCur - i, dp[mirror]);
// 继续扩展 i 的回文长度，只有第三种情况的时候才有效，前两种情况必不满足 prep[start - 1] == prep[end + 1]
int start = i - dp[i], end = i + dp[i];
while (start - 1 >= 0 && end + 1 < size_p && prep[start - 1] == prep[end + 1])
{
--start;
++end;
++dp[i];
}
// 更新 center 和 bCur
if (i + dp[i] > bCur)
{
bCur = i + dp[i];
center = i;
}
}
center = max_element(dp.begin(), dp.end()) - dp.begin();
return s.substr((center - dp[center]) / 2, dp[center]);
}
};