# 【題解】LeetCode 5. Longest Palindromic Substring

【範例】Manacher’s Algorithm
【題目敘述】5. Longest Palindromic Substring
【解題想法】

• (1) Manacher’s Algorithm，O(N)
• (2) DP 找出最長迴文字串，比較慢 O(N^2)

#### Manacher’s Algorithm

```class Solution {
public:
string longestPalindrome(string s) {
int l = s.length(), dp[l*2+5], mxr, mxp, idx = 0;
string ans = "";
memset(dp, 0, sizeof(dp));
char ss[l*2+5];
ss[0] = '#';
ss[1] = '#';
for (int i = 0; i < l; i++){
ss[i*2+2] = s[i];
ss[i*2+3] = '#';
}
l *= 2;
mxr = 0;
mxp = 0;
for (int i = 1; i <= l; i++){
if (i <= mxr){
dp[i] = min(dp[mxp*2-i], mxr-i);
}
if (i + dp[i] >= mxr){
while (ss[i+dp[i]+1] == ss[i-dp[i]-1]) dp[i]++;
}
if (i+dp[i] > mxr){
mxr = i+dp[i];
mxp = i;
}
if (dp[i] > dp[idx]) idx = i;
}
for (int i = idx-dp[idx]; i <= idx+dp[idx]; i++){
if (ss[i] != '#'){
ans += ss[i];
}
}
return ans;
}
};
```

#### DP 找出最長迴文字串

```class Solution {
public:
string longestPalindrome(string s) {
int ansi = 0, ansj = 0;
int l = s.length();
if (l == 0) return "";
int a[l][l];
memset(a, 0, sizeof(a));
for (int i = 0; i < l; i++){
a[i][i] = 1;
}
for (int i = 0; i < l-1; i++){
if (s[i] == s[i+1]){
a[i][i+1] = 1;
ansi = i;
ansj = i+1;
}
}
for (int j = 2; j < l; j++){
for (int i = 0; i < l-j; i++){
if (a[i+1][i+j-1] == 1 && s[i] == s[i+j]){
a[i][i+j] = 1;
ansi = i;
ansj = i+j;
}
}
}
return s.substr(ansi, ansj-ansi+1);
}
};
```