最长回文串

题目描述
对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

解法

    //以left,right的中心，向两边扩展的回文串长度
    int expandCenter(string & s, int left, int right) {
        if (left < 0 || left > right || right >= s.size()) return 0;
        int l = left, r = right;
        while (l >=0 && r < s.size() && s[l] == s[r]) {
            l--; r++;
        }
        return r - l - 1; //回文串长度
    }
    //解法：中心扩展法
    //时间复杂度:O(N*N), 空间复杂度:O(1)
    int getLongestPalindrome(string s, int n) {
        if (s.size() <= 1) return s.size();
        int maxLen = 0, left = 0, right = 0;
        //回文串的中心位置有两类: aa(aa之间的位置), aba(b位置)
        //遍历字符串，每个位置i, 构造两个中心位置，向左右扩展，看起能到达的最长回文长度。
        for (int i = 0; i < s.size() - 1; i++) {
            int len1 = expandCenter(s, i, i);
            int len2 = expandCenter(s, i, i+1);
            if (len1 > maxLen) {
                maxLen = len1;
                left = i - len1/2;
                right = i + len2/2;
            }
            if (len2 > maxLen) {
                maxLen = len2;
                left = i - (len2-1)/2;
                right = i + (len2-1)/2;
            }
        }
        return maxLen;
    }