manacher算法,比動态規劃快一些
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnLxcTO5UzMyAjMxMzMwkTMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
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);
}
};