最长回文子串（leetcode_5）

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

这里我用的是中心扩展算法，但是还有一个特别nb的算法Manacher 算法，这个算法我没咋搞懂，但是这个算法的时间复杂度是O(n)的，中心扩展算法的时间复杂度是O(n^2)的。

中心扩展算法的思路是依次遍历字符串中的每个点，然后由这个点向两边扩展，或者由这个点以及下一个点向两边扩展。（aba和abba都是回文子串）。

#include <iostream>



using namespace std;



class Solution

{

public:

    string longestPalindrome(string s)

    {

        int length = s.size();

        int max_length = 0;

        string max_string = "";



        for (int i = 0; i < length; ++i)

        {

            int size = 0;

            while (i - size >= 0 && i + size < length && s[i - size] == s[i + size])

            {

                size++;

            }

            int current_length = 2 * size - 1;



            if (max_length < current_length)

            {

                max_length = current_length;

                max_string = s.substr(i - size + 1, current_length);

            }

        }



        for (int i = 0; i < length; ++i)

        {

            int size = 0;

            while (i - size >= 0 && i + 1 + size < length && s[i - size] == s[i + 1 + size])

            {

                size++;

            }

            int current_length = 1 > 2 * size ? 1 : 2 * size;



            if (max_length < current_length)

            {

                max_length = current_length;

                max_string = s.substr(i - size + 1, current_length);

            }

        }



        return max_string;

    }

};



int main()

{

    Solution solute;

    cout << solute.longestPalindrome("cbbd") << endl;

    return 0;

}