[leetcode 5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/)
===
[TOC]
###### tags: `DP` `Leetcode` `palindromic`

## Expand Around Center(EAC)
每個字元依序為中心，以他向外擴展找到以他為中心最長的回文串，進而找到解

問題: 奇偶問題，奇數跟偶數都有可能為對稱，例如aba, noon，所以要分開解

search程式碼中，最後的l跟r會跑到匹配回文失敗的字元上，所以start= l+1，而長度變成r-l-1

當字串長度為1時為特殊情況無法處理，此時輸入=輸出

時間複雜度為==O(N^2)==
空間複雜度為==O(1)==

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()== 1) return s;
        int maxLen= 0, n= s.length(), start= 0;

        for(int i= 0; i< n- 1; ++i)
        {
            auto curOdd= search(s, i, i);
            auto curEven= search(s, i, i+ 1);
            auto cur= curOdd.second > curEven.second ? curOdd: curEven;
            if(cur.second > maxLen)
            {
                maxLen= cur.second;
                start= cur.first;
            }
        }

        return s.substr(start, maxLen);
    }

    pair<int, int> search(string& s, int l, int r)
    {
        while(l>= 0 && r< s.length() && s[l] == s[r])
        {
            --l;
            ++r;
        }

        return {l+ 1, r-l- 1};
    }
};

## DP

建構一組dp，dp[i][j]表示字串i到字串j是否為回文，若為否定，則向外擴展必然為否定，反之去匹配新的字元即可，當長度為1時必然回文，長度為2時則要對比兩個字元是否相同

時間複雜度為==O(N^2)==
空間複雜度為==O(N^2)==

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.length(), vector<bool>(s.length()));
        int cur_len= 1;
        pair<int, int> res; // begin, end

        while(cur_len <= s.length())
        {
            int l= 0, r= l+cur_len-1;
            while(r < s.length())
            {
                if(cur_len == 1) dp[l][r]= true;
                else if(cur_len == 2 && s[l] == s[r]) dp[l][r] = true;
                else
                {
                    if(dp[l+1][r-1] && s[l] == s[r]) dp[l][r]= true;
                }
                if(dp[l][r])
                {
                    res.first= l;
                    res.second= r;
                }
                ++l;
                ++r;
            }
            ++cur_len;            
        }

        return s.substr(res.first, res.second- res.first+1);
    }
};

## Optimal, Manacher's Algo

參考: [有圖片](https://cloud.tencent.com/developer/article/1886684)，[有講解](https://bclin.tw/2021/07/22/leetcode-5/)，[展示ALGO過程](http://manacher-viz.s3-website-us-east-1.amazonaws.com/#/)
基於EAC之下去優化的。

首先解決奇偶問題，在每個字元之間插入特殊符號，例如abaabad會變成#a#b#a#a#b#a#d#，長度從7變成15，qwqw變成#q#w#q#w#，長度從4變成9，全部都變成奇數長度

接著用一個P[]儲存以每個字元為中心的回文長度，關鍵在於這次不是每個都暴力算，可以使用回文的特性加速

以下面圖為例子，已知P~L~到P~R~為回文，P為中心點
在看下圖，目前想知道第i位置的回文長度P[i]，則可以以P為中心點找到鏡像點位置j，
下圖可以得知j的最大回文長度P[j]，因為前面會先被算到，此時，P~L~到P~R~為回文，以j為中心的回文長度會跟以i為中心的回文長度相同，因為他們是鏡像的，可以理解成大圈回文內包小圈回文則鏡像也回文，因此P[i]=P[j]

接著需要處理兩個問題:
* 中心點P怎麼找，以下稱中心點為Center, C
* 計算P[i]時有沒有特殊情況，該如何處理

中心點C: 需要多一個變數Right, R，表示可以延伸到最遠的地方，每次找P[i]時都會去維護有沒有更遠的R可以使用，並更新C跟R

特殊情況:

計算P[i]會遇到三種case

case 1: 理想情況，如上面所說，找到鏡像的P[j]是被大的P~L~、P~R~包住，可以直接P[i]= P[j]

case 2: P[j]的長度超出P~L~的範圍，這造成在P~R~後面的不能保證回文，因此P[i]= R- i，先把在大回文裡面的加進來，剩下超出部分再用EAC慢慢找

case 3: 要找的i本身就超出R了，直接EAC找


最後算完P[i]後，怎麼找到答案，列幾個例子就可以找到規律，第i位置的回文對應到原始字串為，start= (i-P[i])/2，長度不變len= P[i]

仍須注意一個字元時無法處理，輸入=輸出

時間複雜度為==O(N)==
空間複雜度為==O(N)==

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.length()== 1) return s;
        auto newStr = addStr(s);
        int n= newStr.length();
        vector<int> P(n, 0);
        int c= 0, r= 0;
        for(int i= 0; i< n; ++i)
        {
            int mirror_i= c-(i-c);

            if(r> i && i+ P[mirror_i] < r)
            {
                P[i] = P[mirror_i];
            }
            else if(r> i && i+ P[mirror_i] > r)
            {
                P[i]= r-i;
                //do EAC
                int l= i-P[i]- 1, r= i+P[i]+ 1;
                while(l>= 0 && r< n && newStr[l] == newStr[r])
                {
                    --l;
                    ++r;
                    ++P[i];
                }
            }
            else
            {
                int l= i-1, r= i+1;
                while(l>= 0 && r< n && newStr[l] == newStr[r])
                {
                    --l;
                    ++r;
                    ++P[i];
                }
            }
            //update c and r
            if(i+P[i] > r)
            {
                c= i;
                r= i+P[i];
            }
        }
        int maxLen= 0, start= 0;
        for(int i= 2; i< n; ++i)
        {
            if(P[i]> maxLen)
            {
                maxLen= P[i];
                start= (i-P[i])/2;
            }
        }

        return s.substr(start, maxLen);

    }


    string addStr(string& s)
    {
        string newStr= "#";

        for(int i= 0; i< s.length(); ++i)
        {
            newStr += s[i];
            newStr += "#";
        }
            

        return newStr; 
    }
};