5. Longest Palindromic Substring

Description Hints Submissions Discuss Solution

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

和上次做的PAT回文串题目一样，只是返回不是最大长度，是最大串，如果有多个相同长度的串，随便输出一个就行了。

原来做的题目连接：http://blog.csdn.net/major_zhang/article/details/64500157

O(N^2)做法：

以i下标为遍历字符串的坐标，左右展开，j为当前遍历的长度。

每次从i开始，要依次判断奇数偶数的情况，取最大值，注意偶数的时候以左边为基准和以右边为基准都可以，关键要在比较的时候控制好。

还有注意左边界是0，右边界是len-1，所以到len就要break

class Solution {
public:
string longestPalindrome(string s)
{


int len = s.length();
int left = 0,right = 0;
int Max = -1;


for(int i = 0; i < len; i++)
{
    //奇数情况
    int ans = 1;
    for(int j = 1; j < len; j++)
    {
        if(i-j<0 || i-j >= len || s[i-j]!= s[i+j])
            break;//跳到下一个下标
        ans+=2;
        if(ans>Max)
        {
            left = i-j;
            right = i+j;
        }
    }
    //每一次下标都取一次最值
    Max = Max<ans?ans:Max;


    //偶数情况
    ans = 0;
    for(int j = 1; j < len; j++)
    {
//                if(i-j+1<0 || i+j>=len ||s[i+1-j] != s[i+j])//偶数以对称点左边的数为基准
        if(i-j<0 || i-1+j>=len ||s[i-j] != s[i-1+j])//偶数以对称点右边的数为基准即abba，起始为
            //偶数的情况
            break;
        ans+=2;
        if(ans>Max)
        {
            left = i-j;
            right = i+j-1;
        }
    }
    Max = Max<ans?ans:Max;
}

//cout<<Max<<endl;
//cout<<left<<" "<<right;
    return s.substr(left,right-left+1);
}

};

O(N^2) 动态规划做法：

dp[i][j] 表示子串s[i…j]是否是回文
初始化：dp[i][i] = true (0 <= i <= n-1); dp[i][i-1] = true (1 <= i <= n-1); 其余的初始化为false
dp[i][j] = (s[i] == s[j] && dp[i+1][j-1] == true)

class Solution {
public:
string longestPalindrome(string s) {
        const int len = s.size();
        if(len <= 1)return s;
        bool dp[len][len];//dp[i][j]表示s[i..j]是否是回文
        memset(dp, 0, sizeof(dp));
        int resLeft = 0, resRight = 0;
        dp[0][0] = true;
        for(int i = 1; i < len; i++)
        {
            dp[i][i] = true;
            dp[i][i-1] = true;//这个初始化容易忽略，当k=2时要用到
        }
        for(int k = 2; k <= len; k++)//枚举子串长度
            for(int i = 0; i <= len-k; i++)//枚举子串起始位置
            {
                if(s[i] == s[i+k-1] && dp[i+1][i+k-2])
                {
                    dp[i][i+k-1] = true;
                    if(resRight-resLeft+1 < k)//???i+k-1 - i = k-1 < k...跟清华数据结构那本书那样的吧
                    {
                        resLeft = i;
                        resRight = i+k-1;
                    }
                }
            }
        return s.substr(resLeft, resRight-resLeft+1);
    }
};

　然后就是O(n)的时间复杂度，需要用到Manacher算法和后缀数组，下面转载自 http://www.cnblogs.com/TenosDoIt/p/3675788.html

算法4：Manacher算法，时间复杂度O(n), 空间复杂度O(n)

该算法首先对字符串进行预处理，在字符串的每个字符前后都加入一个特殊符号，比如字符串 abcd 处理成 #a#b#c#d#,为了避免处理越界，在字符串首尾加上不同的两个特殊字符(c类型的字符串尾部不用加，因为自带‘’)，这样预处理后最终变成$#a#b#c#d#^，经过这样处理后有个好处是原来的偶数长度和奇数长度的回文在处理后的字符串中都是奇数长度。假设处理后的字符串为s 本文地址

对于已经预处理好的字符串我们用数组p[i]来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]）,以字符串“12212321”为例，p数组如下

s： $ # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # ^
p： 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1

可以看出，P[i]-1正好是原字符串中回文串的总长度, 如果p数组已知，遍历p数组找到最大的p[i]就可以求出最长回文的长度，也可以求出回文的位置

下面给出求p[]数组的方法：

设id是当前求得的最长回文子串中心的位置，mx为当前最长回文子串的右边界（回文子串不包括该右边界），即mx = id + p[id]。记j = 2*id – i ，即 j 是 i 关于 id 的对称点。

1、当i < mx 时，如下图。此时可以得出一个非常神奇的结论p[i] >= min(p[2*id - i], mx - i)，下面我们来解释这个结论

如何根据p[j]来求p[i]呢，又要分成两种情况

（1.1）当mx – i > p[j], 这时候以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中，由于 i 和 j 对称，以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中，所以 P[i] 至少等于 p[j], 后面的再继续匹配。如下图

注：这里其实p[i]一定等于p[j],后面不用再匹配了。因为如果p[i]后面还可以继续匹配，根据对称性，p[j]也可以继续扩展了

（1.2）当mx – i <= p[j]，以S[j]为中心的回文子串不完全包含于以S[id]为中心的回文子串中，但是基于对称性可知，下图中两个绿框所包围的部分是相同的，也就是说以S[i]为中心的回文子串，其向右至少会扩张到mx的位置，也就是说 P[i] 至少等于 mx - i，至于mx之后的部分是否对称，就只能老老实实去匹配了。

注：如果mx – i < p[j] ，这时p[i]一定等于mx - i, 因为如果p[i]在mx之后还可以继续匹配，根据对称性，mx之后匹配的点(包括mx)一定会出现在my的前面，这说明p[id]也可以继续扩展了

2、当i >= mx, 无法对p[i]做更多的假设，只能p[i] = 1,然后再去匹配

算法复杂度分析：根据斜体字部分的注释，只有当mx-i = p[j]时以及 i > mx时才要扩展比较，而mx也是在不断扩展的，总体而言每个元素比较次数是n的线性关系，所以时间复杂度为O(n)

class Solution {
public:
    string longestPalindrome(string s) {
        const int len = s.size();
        if(len <= 1)return s;
        //Manncher算法 ，o（n）
        string str = preProcess(s);
        int n = str.size(), id = 0, mx = 0;
        vector<int>p(n, 0);
        for(int i = 1; i < n-1; i++)
        {
            p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
            //if(mx <= i || (mx > i && p[2*id-i] == mx - i)) //根据正文斜体部分的注释，这里可要可不要
            while(str[i+p[i]] == str[i-p[i]])p[i]++;
            if(i + p[i] > mx)
            {
                mx = i + p[i];
                id = i;
            }
        }
         
        //遍历p，寻找最大回文长度
        int maxLen = 0, index = 0;
        for(int i = 1; i < n-1; i++)
            if(p[i] > maxLen)
            {
                maxLen = p[i];
                index = i;
            }
        return s.substr((index - maxLen)/2, maxLen-1);
    }
    //预处理字符串，abc预处理后变成$#a#b#c#^
    string preProcess(const string &s)
    {
        int n = s.size();
        string res; 
        res.push_back('$');//把$放到字符串头部
        res.push_back('#');//以#作为原来字符串中每个字符的间隔
        for(int i = 0; i < n; i++)
        {
            res.push_back(s[i]);
            res.push_back('#');
        }
        res.push_back('^');//以^作为字符串的结尾
        return res;
    }
};

算法5：可以用后缀数组来解，在源字符串后面加一个特殊字符，然后把源字符串的反转串连接到源字符串后面，那么问题就变成了求这个新字符串的某两个后缀的最长公共前缀，该问题是典型的后缀数组应用，可以参考here，关于后缀数组请关注我的后续博客