LeetCode HOT100 - 最长回文子串

仍然可以用 manacher

板子的回顾这里就不重复贴了，可以看 https://www.cnblogs.com/rdcamelot/p/19753872

这里没有什么本质的区别，就是要额外记录一下回文串是什么样的

vector<int> manacher(string s) {string t = "#";for (auto c : s) {t += c;t += '#';}int n = t.size();vector<int> r(n);for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + r[j] > i) {r[i] = min(r[2 * j - i], j + r[j] - i);}while (i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]) {r[i] += 1;}if (i + r[i] > j + r[j]) {j = i;}}return r;
}class Solution {
public:string longestPalindrome(string s) {int ans = 0;auto r = manacher(s);string res;for (int i = 0; i < r.size(); i++) {if (r[i] - 1 > ans) {ans = r[i] - 1;int R = (r[i] - 1) / 2;if (i & 1) {string tmp = s.substr(i / 2 + 1, R);res = s[i / 2] + tmp;reverse(tmp.begin(), tmp.end());res = tmp + res;} else {string tmp = s.substr(i / 2, R);res = tmp;reverse(tmp.begin(), tmp.end());res = tmp + res;}}}return res;}
};