题解 | #最长回文子串#

int min(int a,int b)
{
    if(a < b)
        return a;
    return b;
}
int max(int a,int b)
{
    if(a > b)
        return a;
    return b;
}

int getLongestPalindrome(char* A ) 
{
    int len = strlen(A);
    char a[2*len + 1];//扩展后的字符串
    int a_len = 0;
    for(int i = 0;i < len;i++)//对字符串添加不属于里面的特殊字符，来让所有的回文串都变成奇数形式。
    {
        a[a_len] = '#';
        a_len++;
        a[a_len] = A[i];
        a_len++;
    }
    a[a_len] = '#';
    a_len++;
    
    int ans = 0;
    int mid = 0;//当前回文子串的中心
    int right = 0;//当前回文子串的最右边的位置
    int lens[2*len + 1];//用来存放以当前下标的元素为中心的回文串长度
    for(int i = 0;i < a_len;i++)//遍历扩展后的字符串
    {
        if(i < right)
        {
            lens[i] = min(right-i,lens[2*mid-i]);
        }
        else
            lens[i] = 0;
        
        while( ( (i-lens[i]-1)>=0 && (i+lens[i]+1)<a_len) && a[ (i-lens[i]-1) ]==a[ (i+lens[i]+1) ] )
        {
            lens[i] = lens[i]+1;
        }
        if(i+lens[i] > right)//更新当前回文串的中心元素位置和最右边的为位置
        {
            right = i+lens[i];
            mid = i;
        }
        
        ans = max(ans,lens[i]);//获得最长回文串的长度
    }
    
    return ans;
}