leetcode 5. Longest Palindromic Substring 回文串处理

0 问题：求一个串中，最长的连续子回文串的长度

1 这个问题是求串的连续子串问题，连续子串为o(n^2)，而比较是否为回文串为o(n0)，所以这题目的暴力解法时间复杂度为o(n^2)，我们希望用更少的时间来解决。这题目的思路为从回文串的“肚子”着手，向两边进行扩充；

2 代码

    string longestPalindrome(string s)
    {
        int n = s.size();
        if (n == 0 || n == 1)
            return s;
        int j, k, i;
        int maxlen = 0, maxstart = 0, nowlen;
        for (i = 0; i < n;)
        {
            if (maxlen /2 + i >= n)
                break;
            j = i, k = i;
            while (k < n && s[k] == s[k + 1])
                k++;
            i = (k + j) / 2 + 1;
            while (j > 0 && k < n && s[j - 1] == s[k + 1])
            {
                j--, k++;
            }
            nowlen = k - j + 1;
            if (nowlen > maxlen)
            {
                maxlen = nowlen;
                maxstart = j;
            }
        }
        return s.substr(maxstart, maxlen);
    }

3 分析

代码中i为每次比较的中点，j和k分别为最左和最右两个下标。这里面有几个加速的地方：1,maxlen/2+i>=n break 这里的意义是当i一直增长到某一个点，他最多的半径只能是maxlen/2否则就溢出了，到这个地方的时候就用再继续尝试了. 2,while() k++ 这里是代表如果中点i附近为有多个相同的数据的话，那么直接可以进行自增，就不用再相互比较了。 3,i = (k+j)/2+1 这里是用k与j的关系来替代每次i的自增，好处为当某一次的k-j很长的时候，i可以一次性移动多一些距离，而不用一个个移动。如串aaaaaaa，这样的话i可以一次移动到中点，而不是一个个移动，从而提升效率。