题解 | #NC17-最长回文子串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param A string字符串 
 * @param n int整型 
 * @return int整型
 */
/****************************************************************
* 双指针中心扩散，设置左指针left和右指针right，分别位于对称中心两侧
* 左右指针向两侧扩散，中心对称点是重复字符则当场一个字符处理
* 例1、abbbba,i指向第1个b时，right指向第2个b，step++了4次指向最后一个a
* 此时left指向第1个a，满足2个while循环，right++后值为6，left--后值为-1
* right-left-1=6-(-1)-1=6，即为回文子串长度
************************************************************/
int getLongestPalindrome(char* A, int n ) {
    // write code here
    int left, right;
    int len = 0;
    int step;
    
    if(n == 0)
        return 0;
    
    for(int i = 0; i < n; i = i+step)
    {
        step = 1;
        left = i-1;
        right = i+1;
        //中心对称点是重复字符则当场一个字符处理
        while(A[right] != '\0' && A[right] == A[i])
        {
            right++;
            step++;
        }
        //核心算法：A[left] == A[right]，注意边界条件left >=0和A[right] != '\0'
        while(left >=0 && A[right] != '\0' && A[left] == A[right])
        {
            left--;
            right++;
        }
        //回文串长度即为right-left-1 
        if(right-left-1 > len)
            len = right-left-1;
    }
    
    return len;
}