题目描述：

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

　　这是一道很有名的题目，相信很多人面试的时候会被问到。

　　本人算法能力一般，题目看完毫无头绪。苦思冥想大半天，才想到用动态规划。代码写的很丑，就不贴了。结果一提交，系统提示Time Limit Exceeded。

这说明算法复杂度太高。我又抓耳挠腮大半天，想到了中心扩展法。提交通过，很是开心。

中心扩展法：

string longestPalindrome(string s) {
    int len = s.size();
    if(len < 2)
        return s;
    int maxlen = 1;
    int start = 0;
    int low,high;
    for (int i = 1;i < len;++i)
    {
        low = i - 1;
        high = i;
        while (low >= 0 && high < len && s[low] == s[high])
        {
            --low;
            ++high;
        }
        if (high - low - 1 > maxlen)
        {
            maxlen = high - low - 1;
            start = low + 1;
        }
        low = i - 1;
        high = i + 1;
        while (low >= 0 && high < len && s[low] == s[high])
        {
            --low;
            ++high;
        }
        if (high - low - 1 > maxlen)
        {
            maxlen = high - low - 1;
            start = low + 1;
        }
    }
    return string(s,start,maxlen);
}

　　走到这一步已经很不容易，上网一搜，发现还存在一个更牛的解法，如下：

Manacher's algorithm

string preProcess(const string &s)
{
    int n = s.size();
    string res = "$";
    for (int i = 0;i < n;++i)
    {
        res += "#";
        res += s[i];
    }
    res += "#^";
    return res;
}

string longestPalindrome(string s){
    if(s.size() < 2)
        return s;
    string str = preProcess(s);
    int n = str.size();
    int *p = new int[n];
    int id = 0, mx = 0;
    for (int i = 1;i < n-1;++i)
    {
        p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
        while(str[i+p[i]] == str[i-p[i]])
            ++p[i];
        if (i + p[i] > mx)
        {
            mx = i + p[i];
            id = i;
        }
    }

    int maxlen = 0, index = 0;
    for (int i = 1;i < n-1;++i)
    {
        if (p[i] > maxlen)
        {
            maxlen = p[i];
            index = i;
        }
    }
    delete [] p;
    return string(s,(index - maxlen)/2,maxlen-1);
}

　　这里引用别人的一段话：

　　　　　　This algorithm is definitely non-trivial and you won’t be expected to come up with such algorithm during an interview setting.

　　　　　　But, please go ahead and understand it, I promise it will be a lot of fun.

　　　　　　想了解原理的可以参考这篇文章http://www.cnblogs.com/tenosdoit/p/3675788.html

 

转载于:https://www.cnblogs.com/gattaca/p/4169515.html