---
tags: Leetcode
topic: 5. Longest Palindromic Substring
---
# 5. Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
>Given a string s, return the longest palindromic substring in s.

## Manacher's Algorithm

#define MIN(a,b) (a<b)?a:b 

char * longestPalindrome(char * s){
    int s_len = strlen(s);
    char * s2 = s;
    char *new_s = calloc(2*s_len+1,sizeof(char)); 
    //--- add # in new string
    int count = 0;
    for(int i = 0; i<s_len;i++){
        new_s[count] = '#';
        count ++;
        new_s[count] = s[i];
        count ++;
    }
    new_s[count] = '#';
    int mirror = 0;
    int maxright = 0;
    int center = 0;
    int maxLen = 1;
    int begin =0;
    int * table = calloc(2*s_len+1,sizeof(int));
    
    for(int i = 0; i<2*s_len+1 ; i++){
        if(i<maxright){
            mirror = 2*center-i;
            table[i]=MIN(maxright-i,table[mirror]);
        }
        //--- center
        int left = i-(1+table[i]);
        int right = i+(1+table[i]);
        while(left>=0 && right<(2*s_len+1)&&new_s[left] == new_s[right]){
            left--;
            right++;
            table[i]++;
        }
        // update maxright + center
        if(i+table[i]>maxright){
            maxright = i+table[i];
            center = i;
        }
        if(table[i] > maxLen){
            maxLen = table[i];
            begin = (i-maxLen)>>1;
        }
    }
    char * ans = malloc((maxLen+1)*sizeof(char));
    for(int j =0;j<maxLen; j++){
        ans[j] = s2[begin];
        begin++;
        
    }
    ans[maxLen] = '\0';
    return ans;
}