LeetCode 5. Longest Palindromic

思路：有两种
1.dp
dp[i][j] = 1 when dp[i+1][j-1] == 1&&s[i]==s[j]
dp[i][j] = 0 when dp[i+1][j-1] = 0
dp[i][i] = 1
dp[i][i+1] = s[i]==s[j]? 1:0;()注意此时要更新start 和 longest

class Solution {
public:
    /*
    回环有两种，abba,aba
    abcd,abc
    用DP[i][j] = 1 ||0
    */
    
    string longestPalindrome(string s) {
        int n = s.size();
        vector<vector<int>> dp(n,vector<int>(n));
        int start = 0;
        int longest = 1;
        for(int i =0;i<n;i++){
            dp[i][i] = 1;
            if(i<n-1){
                if(s[i] == s[i+1])
                {
                    start = i;
                    longest = 2;
                    dp[i][i+1] = 1;
                }else
                    dp[i][i+1] = 0;
            }
        }

        for(int l = 3;l<=n;l++)
            for(int i =0;i+l-1<n;i++)
            {
                int j = i+l-1;
                if(dp[i+1][j-1] ==1 &&s[i] == s[j])
                {
                    dp[i][j] = 1;
                    start = i;
                    longest = l;
                } 
                
            }
        return s.substr(start,longest);
    }
};

Manacher算法，具体过程可以看https://www.cnblogs.com/mini-coconut/p/9074315.html，但是他的代码有错误哦

start = (i-l[i]+1)/2

class Solution {
public:
    string longestPalindrome(string s) {
        string ms = "#";
        for(auto c:s)ms =ms+c+"#";
        int n = ms.size();
        if(n<3)return "";
        vector<int> l(n,1);
        int pos = 0,mx=0;
        int start = 0,longest = 1;
        for(int i =0;i<n;i++){
            //首先 i在mx范围内吗，内可以赋对称的值，外初始为1
            l[i] = i<mx?min(l[2*pos-i],mx-i):1;
            //继续找最大子串
            while(l[i]+i<n&&i-l[i]>-1&&ms[i-l[i]] == ms[i+l[i]])l[i]++;
            //更新结果
            if(l[i]+i>mx)
            {
                pos = i;
                mx = l[i]+i;
            }
            if(l[i]-1>longest)
            {
                start = i-l[i]+1;
                longest =l[i]-1;
            }
        }
        
        return s.substr(start/2,longest);
    }
};