首页 > 代码库 > Longest Palindromic Substring(最长回文子串)

Longest Palindromic Substring(最长回文子串)

题目描述:

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

 

Longest Palindromic Substring(最长回文子串)