# Longest Palindromic Substring

###### tags: `Medium`

參考網站:
https://web.ntnu.edu.tw/~algo/Palindrome.html

https://www.cnblogs.com/grandyang/p/4464476.html

- 大神解法
目前有兩種解法比較優，Dynamic programming 跟 Manacher's Algorithm
思路:
記憶體換執行速度，
記憶體使用少於:61%
速度快於:92%

class Solution {
public:
    string longestPalindrome(string s) {
        string ss = "#"; 
        for (auto& ch : s) {
            ss.push_back(ch); 
            ss.push_back('#'); 
        }
        
        int n = ss.size(), ii = 0, most = 0; 
        vector<int> hlen(n); 
        
        for (int i = 0, center = 0, right = 0; i < n; ++i) {
            if (i < right) hlen[i] = min(right-i, hlen[2*center-i]); 
            while (0 <= i-1-hlen[i] && i+1+hlen[i] < n && ss[i-1-hlen[i]] == ss[i+1+hlen[i]]) ++hlen[i]; 
            if (right < i+hlen[i]) center = i, right = i+hlen[i]; 
            if (most < hlen[i]) ii = i, most = hlen[i]; 
        }
        return s.substr((ii-most)/2, most); 
    }
};