题目

ongest-palindromic-substring

算法

DP

O(n^2)

• dp[i][j]:字符串区间[i,j]是否是回文串
• i=j，只有一个字符，是回文串
• i=j+1,两个字符，判断s[i]是否等于s[j]
• i-j>=2，除了判断s[i]和s[j]还需要 判断dp[j+1][i-1]是否是真 若是真，则为回文串

manacher

O(n)算法

http://www.cnblogs.com/grandyang/p/4475985.html

• 加入特殊符号$:可以不用特殊处理越界问题

代码

* DP

class  Solution{
public:
    string longestPalindrome(string s){
        int dp[s.size()][s.size()]={0},left=0,right=0,len=0;
        for(int i=0;i<s.size();++i){
            for(int j=0;j<i;++j){
                dp[j][i]=(s[i]==s[j]&& (i-j<2 ||dp[j+1][i-1]));
                if(dp[j][i]&& len<i-j+1){
                    len=i-j+1;
                    left=j;
                    right=i;
                }
            }
            dp[i][i]=1;
        }

        return s.substr(left,right-left+1);
    }
};

* manacher

class Solution {
public:
    string longestPalindrome(string s) {
        string t ="$#";
        for (int i = 0; i < s.size(); ++i) {
            t += s[i];
            t += '#';
        }
        int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0;
        for (int i = 0; i < t.size(); ++i) {
            p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;
            while (t[i + p[i]] == t[i - p[i]]) ++p[i];
            if (mx < i + p[i]) {
                mx = i + p[i];
                id = i;
            }
            if (resMx < p[i]) {
                resMx = p[i];
                resId = i;
            }
        }
        return s.substr((resId - resMx) / 2, resMx - 1);
    }
};