# LPS
Longest Palindromic Substring(最常迴文子字串)

## Manacher's Algorithm

O(n)演算法,以中心拓展法為基礎,利用迴文性質,先求出該點為中心時最小的回文子字串,再利用中心擴展法找到額外的回文子字串

1. 先在字串的每個字元中插入一個特殊符號,包括頭尾

string str="#";
for(int i=0;i<s.size();i++){
    str+=s[i];
    str+='#';
}

2. 每次遍歷都會維護當前最大的子回文

vector<int> p(str.size());  //p[i]=以i為中心點向外擴張的回文半徑
int R=0,C=0;  //C=當前最大回文的中心點,R=當前最大回文的右界

for(int i=0;i<str.size();i++){
    .
    .
    .
    if(i+p[i]>R){
        R=i+p[i];
        C=i;
    }
}

3. 接著遍歷,i如果在最大回文裡,可由鏡射獲得最基本的回文半徑,因為回文性質,在回文內都是對稱的

vector<int> p(str.size());
int R=0,C=0;

for(int i=0;i<str.size();i++){
    if(i<R){  //如果i在最大回文裡
        int mirror=C-(i-C);  //最大回文裡鏡射到的元素編號
        p[i]=min(R-i,p[mirror]);  //和R-i取min,因為不可越界,越界後無法保證和外面的字串有回文
    }else{
        p[0]=0;
    }
    .
    .
    if(i+p[i]>R){
        R=i+p[i];
        C=i;
    }
}

4. 中心拓展法找到額外的回文

vector<int> p(str.size());
int R=0,C=0;

for(int i=0;i<str.size();i++){
    if(i<R){
        int mirror=C-(i-C);
        p[i]=min(R-i,p[mirror]);
    }else{
        p[0]=0;
    }
    
    while(i-1-p[i]>=0 && i+1+p[i]<str.size() && str[i-1-p[i]]==str[i+1+p[i]]){  //中心拓展法,要注意邊界條件
        p[i]++;
    }
    .
    .
    if(i+p[i]>R){
        R=i+p[i];
        C=i;
    }
}

5. 更新最大回文半徑和中心點

vector<int> p(str.size());
int R=0,C=0;

int len=0,center;
for(int i=0;i<str.size();i++){
    if(i<R){
        int mirror=C-(i-C);
        p[i]=min(R-i,p[mirror]);
    }else{
        p[0]=0;
    }
    
    while(i-1-p[i]>=0 && i+1+p[i]<str.size() && str[i-1-p[i]]==str[i+1+p[i]]){
        p[i]++;
    }
    
    if(p[i]>len){
        len=p[i];
        center=i;
    }
    
    if(i+p[i]>R){
        R=i+p[i];
        C=i;
    }
}

6. 最大回文就是str的$\frac{C-len}{2}$~$\frac{C+len}{2}-1$，$-1$是因為要扣掉一個#字號，每個回文前後一定都是#字號

string ans;
ans=s.substr((center-len)/2,len);

完整Code

string longestPalindrome(string s) {
    string str="#";
    for(int i=0;i<s.size();i++){
        str+=s[i];
        str+='#';
    }
    
    int R=0,C=0,len=0,center=0,n=str.size();
    vector<int> p(n);
    
    for(int i=0;i<n;i++){
        if(i<R){
            int mirror=C-(i-C);
            p[i]=min(R-i,p[mirror]);
        }else{
            p[0]=0;
        }

        while(i-1-p[i]>=0 && i+1+p[i]<n && str[i-1-p[i]]==str[i+1+p[i]]){
            p[i]++;
        }

        if(p[i]>len){
            len=p[i];
            center=i;
        }

        if(i+p[i]>R){
            R=i+p[i];
            C=i;
        }
    }

    string ans;
    ans=s.substr((center-len)/2,len);
    return ans;
}

## Dynamic Programming

利用botton-up來求(bool)dp[l][r]間是否是回文

dp狀態轉移如下:

bool dp[MAXN][MAXN]; //字串s[l, r]是不是回文

//Case 1 
if(l==r) dp[l][r]=true;
//Case 2
if(s[l]==s[r] && l+1==r) dp[l][r]=true;
//Case 3
if(s[l]==s[r]) dp[l][r]=dp[l+1][r-1];
//Case 4
if(s[l]!=s[r]) dp[l][r]=false;

1. Case 1代表只剩一個字元,回文長度為1
3. Case 2代表只剩兩個字元,且兩個字元相同,回文長度為2
4. Case 3代表兩個不相鄰的字元相同,則dp[l][r]=dp[l+1][r-1]
如果中間不是回文則當前substring也不是回文
如果中間是回文則當前substring是回文,回文長度為r-l+1
4. 如果兩個字元不是回文則當前substring不是回文

<a href="https://leetcode.com/problems/longest-palindromic-substring/">LeeCode : Longest Palindromic Substring</a>

button_up(AC)

string longestPalindrome(string s){
    int n=s.size();
    vector<vector<bool>> dp(n+1,vector<bool>(n+1,0));
    int ans=0,idx;
    for(int l=n;l>0;l--){
        for(int r=l;r<=n;r++){
            if(l==r){
               dp[l][r]=true;
            }else if(s[l-1]==s[r-1]){
               if(r-l==1) dp[l][r]=true;
               else dp[l][r]=dp[l+1][r-1];
            }
            if(dp[l][r] && r-l>=ans){
                ans=r-l+1;
                idx=l-1;
            }
        }
    }
    return s.substr(idx,ans);
}

top-down(TLE)

int ans,idx;
bool dp[1000][1000];
bool vis[1000][1000];

bool dpf(int l,int r,string s){
    if(l>r) return 0;
    if(vis[l][r]) return dp[l][r];
    bool result=false;
    
    if(l==r){
       result=true;
    }else if(s[l-1]==s[r-1]){
       if(r-l==1) result=true;
       else result=dpf(l+1,r-1,s);
    }
    if(result && r-l>=ans){
        ans=r-l+1;
        idx=l-1;
    }
    
    dpf(l,r-1,s);
    dpf(l+1,r,s);
    
    dp[l][r]=result;
    vis[l][r]=true;
    return dp[l][r];
}


class Solution {
public:
    string longestPalindrome(string s) {
        ans=0,idx=0;
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        dpf(1,s.size(),s);
        return s.substr(idx,ans);
    }
};

另一種想法

string longestPalindrome(string s){
    int n=s.size();
    vector<vector<int>> dp(n+1,vector<int>(n+1,0));
    int ans=0,idx;
    for(int l=n;l>0;l--){
        for(int r=l;r<=n;r++){
        
            if(l==r) dp[l][r] = 1;
            else if(s[l-1]==s[r-1] && l+1==r) dp[l][r] = 2;
            else if(s[l-1]==s[r-1]) dp[l][r] = (dp[l+1][r-1]!=0?dp[l+1][r-1]+2:0);
            else dp[l][r] = 0;

            if(dp[l][r]>ans){
                ans=dp[l][r];
                idx=l-1;
            }
        }
    }
    return s.substr(idx,ans);
}