Longest Palindromic Substring

给出一个string，看看里面最长palindrome的substring是什么。

4种解法：

1）终极暴力：枚举起点，枚举终点，遍历起点到终点，时间复杂度n^3

2）次暴力：枚举中间位置，向左右延伸求最长，时间复杂度n^2

3）空间DP：dp[i][j] = dp[i+1][j-1] + 2 if..... 时间复杂度和空间复杂度均为 n^2

4） 对于最长回文子串问题有对应O(N)算法--Manacher算法 太难不考

以下解法为第二种

code

// Example program
#include <iostream>
#include <string>
#include <vector>

using namespace std;

string helper(const string& str, int l, int r)
{
    while(l >= 0 && r < (int)str.length() && str[l] == str[r])
    {
        l--;
        r++;
    }

    return str.substr(l+1, r-l-1);
}

string longestsubpalindrome(const string& str)
{
    string ret;
    if(str.empty())
    {
        return ret;   
    }

    ret = str.substr(0,1);

    for(int i = 0; i<(int)str.length(); i++)
    {
        string str1 = helper(str, i, i);
        string str2 = helper(str, i, i+1);
        string cur = str1.length()>str2.length()?str1:str2;
        if(cur.length() > ret.length())
        {
            ret = cur;   
        }
    }

    return ret;
}

int main()
{
    string str = "a";
    cout<<longestsubpalindrome(str)<<endl;
    return 1;
}