【牛客题霸题解】最长回文子串

暴力解法

首先我们来看暴力的解法
例：

纯暴力解法：
以每一个字符为回文的中心往两边扩，看能扩出来的最长回文子串是多长（但是这种只局限于长度是奇数的回文子串）
例子中“abba”这种长度为偶数的回文子串就不太好判断了

解决方案：
给字符串添加辅助字符
#a#b#c#1#2#3#4#3#2#1#a#b#b#a#

找到的最长回文子串为
#1#2#3#4#3#2#1#
#a#b#b#a#
除2可以获得原回文子串的长度

代码

class Solution{
public:
    int getLongestPalindrome(string A, int n) {
        string S = "#";
        for(int i = 0 ; i < n ; i ++)
        {
            S+=A[i];
            S+="#";
        }
        vector<int> Len(S.length());
        int ans = 0;
        for(int i = 0 ; i < S.length() ; i++)
        {
            int len = 1;
            while((i-len>=0&&i+len<S.length())&&S[i-len]==S[i+len])
            {
                len++;
            }
            Len[i]=len-1;
            ans = max(Len[i]*2+1,ans);
        }
        return ans/2;
    }
};

但是，如果使用上述暴力解法的话，类似（aaaaaaaaaaaa....aaaaaaaaaaaa）这种情况运行时间会很差

Manancher算法-O(n)时间复杂度解决最长回文子串问题

（马拉车算法）

Step1 给原字符串加辅助字符

Step2 计算以每一个位置为中间的回文子串的长度 （在这里做优化）

我们定义R表示之前访问过的最右的位置
例如：（例子为了看起来方便，没有写出辅助字符）

我们当前访问的元素是b，但是之前访问f的时候，回文子串扩到了t的位置
所以R就等于t位置的下标
f位置的下标我们记作Mid（即产出最远位置的中心字符）
F位置对应的回文的回文半径为6

备注：访问时从前往后访问的，所有当我们访问到b的时候，之前的所有元素都访问过了，这个时候我们已经知道之前所有元素能扩展出来的回文半径是多长，以及R是多少。

即：①i>=R 暴力
② L_ > L//在边界内 Len[i] = Len[i_]
L_ < L//在边界外 Len[i] = R-i;
L_ == L//相等 从边界开始继续暴力回文判断

c++版本代码

class Solution{
public:
    int getLongestPalindrome(string A, int n) {
        string S = "#";
        for(int i = 0 ; i < n ; i ++)
        {
            S+=A[i];
            S+="#";
        }
        int ans = 0;
        int R = 0;
        int L = 0;
        int Mid = 0;
        vector<int> Len(S.length());
        for(int i = 0 ; i < S.length() ; i++)
        {
            if(i >= R)
            {
                int len = 0;
                while((i-len >=0 && i+len< S.length())&&S[i-len]==S[i+len])
                {
                    len++;
                }
                Len[i] = len-1;
            }
            else{
                int i_ = Mid-(i-Mid);
                int L_ = i_-Len[i_];
                if(L_ > L)//在边界内
                {
                    Len[i] = Len[i_];
                }
                else if(L_ < L)//在边界外
                {
                    Len[i] = R-i;
                }
                else{
                    int len = R-i+1;
                    while((i-len >=0 && i+len< S.length())&&S[i-len]==S[i+len])
                    {
                        len++;
                    }
                    Len[i] = len-1;
                }
            }
            if(i+Len[i] > R)
            {
                Mid = i;
                R = i + Len[i];
                L = i - Len[i];
            }
            ans = max(ans,Len[i]*2+1);
        }
        return ans/2;
    }
};

java

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        StringBuffer S = new StringBuffer("#");
        for(int i = 0 ; i < n ; i ++)
        {
            S.append(A.charAt(i));
            S.append("#");
        }
        int ans = 0;
        int R = 0;
        int L = 0;
        int Mid = 0;
        int[] Len = new int[S.length()];
        for(int i = 0 ; i < S.length() ; i++)
        {
            if(i >= R)
            {
                int len = 0;
                while((i-len >=0 && i+len< S.length())&&S.charAt(i-len)==S.charAt(i+len))
                {
                    len++;
                }
                Len[i] = len-1;
            }
            else{
                int i_ = Mid-(i-Mid);
                int L_ = i_-Len[i_];
                if(L_ > L)//在边界内
                {
                    Len[i] = Len[i_];
                }
                else if(L_ < L)//在边界外
                {
                    Len[i] = R-i;
                }
                else{
                    int len = R-i+1;
                    while((i-len >=0 && i+len< S.length())&&S.charAt(i-len)==S.charAt(i+len))
                    {
                        len++;
                    }
                    Len[i] = len-1;
                }
            }
            if(i+Len[i] > R)
            {
                Mid = i;
                R = i + Len[i];
                L = i - Len[i];
            }
            ans = Math.max(ans,Len[i]*2+1);
        }
        return ans/2;
    }
}

python

# -*- coding:utf-8 -*-

class Solution:
    def getLongestPalindrome(self, A, n):
        # write code here
        S = "#"
        for i in range(0,n):
            S+=A[i]
            S+="#"
        ans = 0
        R = 0
        L = 0
        Mid = 0
        Len = [0]*len(S)
        for i in range(0,len(S)):
            if i >= R:
                LEN = 0;
                while i-LEN >=0 and i+LEN< len(S) and S[i-LEN]==S[i+LEN]:
                    LEN=LEN+1
                Len[i] = LEN-1
            else:
                i_ = Mid-(i-Mid)
                L_ = i_-Len[i_]
                if L_ > L:#//在边界内
                    Len[i] = Len[i_]
                elif L_ < L:#//在边界外
                    Len[i] = R-i;
                else:
                    LEN = R-i+1;
                    while i-LEN >=0 and i+LEN< len(S) and S[i-LEN]==S[i+LEN]:
                        LEN = LEN+1
                    Len[i] = LEN-1
            if i+Len[i] > R:
                Mid = i
                R = i + Len[i]
                L = i - Len[i]
            ans = max(ans,Len[i]*2+1);
        return ans//2;