如何找到字符串中的最长回文子串？

川长思鸟来 2022-08-29 00:15 192阅读 0赞

**什么是回文串？**

回文串其实就是正读和反读一样的字符串，那我们如何判断一个字符串是回文串？其实实现逻辑也比较简单，我们只需要使用双指针，一个从前往后遍历，一个从后往前遍历，关注遇到的字符是否相等即可。

![20210809133826524.png][]

代码如下：

private static boolean isPalindromeString(String s) {
            if (s == null || s.length() == 0) {
                return true;
            }
            int left = 0;
            int right = s.length() - 1;
            while (left < right) {
                if (s.charAt(left) != s.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }

判断一个字符串是回文串的逻辑比较简单，但是正如文章的题目，如何判断一个字符串中**最长的回文子串。**如

abcdcef 最长回文子串就是cdc  
adaelele 其中ada是回文子串，elele也是回文子串，但是elele才是最长回文子串

针对这个问题该如何求解？

**一、暴力搜索**

可以找出所有的子串，再判断子串是否是回文串，最终求得最长的回文子串，代码如下：

private String findLongestPalindromeString(String s) {
            if (s == null || s.length() == 0) return s;
            String maxLengthString = "";
            for (int i = 0; i < s.length(); i++) {
                for (int j = i + 1; j <= s.length(); j++) {
                    //找出所有子串
                    String subString = s.substring(i, j);
                    if (isPalindromeString(subString) && subString.length() > maxLengthString.length()) {
                        maxLengthString = subString;
                    }
                }
            }
            return maxLengthString;
        }

代码比较简单，但是我们可知该方法的时间复杂度是O(![N^\{3\}][N_3])，时间复杂度是比较高的。接下来看看其他解法

**二、基于动态规划的解法**

我们首先定义如下状态：

![20210809150526328.png][]

那我们要知道 p\{ i, j \}，只要我们知道p\{ i+1 , j-1 \}和s\[i\] 、s\[j\]就可以知道了。

（1）当p\[i+1,j-1\] 是false时，表示s\[i+1,j-1\]对应的子串不是回文串，所以自然s\[i,j\]对应的子串也不会是回文串

（2）当p\[i+1,j-1\] 是true时，表示s\[i+1,j-1\]对应的子串是回文串，如果s\[i\] = s\[j\]，那p\[i,j\] = true,表示s\[i,j\]子串是回文串，如果s\[i\]!=s\[j\]，p\[i,j\]=false，表示s\[i,j\]对应的字符串不是回文串。

其实可以表示为如下动态转移方程：P(i,j)=(P(i+1,j−1)&&S\[i\]==S\[j\])

![20210809151923449.png][]

边界条件

当i = j时，表示就一个字符，一个字符肯定是回文串，当 j - i = 1时，表示子串就两个字符，只需要判断 位置 i 与 位置 j 对应的字符是否相等即可。

下面以字符串 **abaelele** 进行说明（注：下图中未填写数字的地方表示false，使用F表示，true用T表示）

（1）当 i = j 时，表示一个字符的子串，即**长度为1**的子串已经处理完毕，初始化后状态如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70][]

（2）接下来我们来看下**长度为2**的子串，那如何获取长度为2的所有子串？其实实现逻辑也很简单，使用 **L** 表示当前处理的长度，当使用 left 表示当前处理的左边界，当知道 L 和 left，其实right便可以计算出来了，即 right = left + L -1，可以使用如下框架辅助理解。

private void findLongestString(String s) {
            //定义当前处理的长度，当然可以使用循环解决
            int L = 2;
    
            /*
             * 1、定义left表示子串的left边界
             * 2、其实left的终止条件可以优化，优化为 left <= s.length - L，因为left > s.length - L 时right就越界了。
             * */
            for (int left = 0; left < s.length(); left++) {
                //计算出right边界，right = left + L -1，关注边界
                int right = left + L - 1;
                if (right > s.length() - 1) {
                    //越界，直接break
                }
                //处理其他业务逻辑
            }
        }

我们前面说过，当 right - left = 1时，表示子串就两个字符，那直接判断left处的字符和right处的字符是否相等即可。当L等于2时，填充以下阴影范围内的值，根据给定的字符串，当L等于2时，会依次形成如下范围内的字符

> （1）当 left = 0时，计算出的 right = 1，处理子串S\[0,1\] = ab，即ab不是回文串  
> （2）当 left = 1时，计算出的 right = 2，处理子串S\[1,2\] = ba,  
> （3）当 left = 2时，计算出的 right = 3，处理子串S\[2,3\] = ae,  
> （4）......依次类推  
> （5）当left = 6时，计算出的 right = 7，处理子串S\[6,7\] = le,此时right已经到达有边界，不需要处理

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1][]

（3）当L=3时，此时根据递推公示P(i,j)=(P(i+1,j−1)&&S\[i\]==S\[j\])，就可以利用前面算出的结果了。当L等于3时，处理如下的阴影部分的面积，即 L=3 指向的阴影部分。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2][]

其实处理逻辑还是比较简单的，根据 P(i,j)=(P(i+1,j−1)&&S\[i\]==S\[j\]) 递推公式，当我们出来P\[0,2\]时（**其实对应的子串就是S\[0,2\] = aba** ），其实可以转换为P\[1,1\] && S\[0\] == S\[2\]，根据第一步计算出的结果，我们其实是可以得出P\[1,1\] = true 的，而S\[0\] == S\[2\] == a。所以P\[0,2\]是等于true。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3][]

其实我们可以发现问题的规模变小了，而且我们也利用上前面计算出的结果，比如计算P\[0,2\]，我们用上了L=1时计算出的P\[1,1\]的结果。

（4）L = 4 和 L = 5时其实道理是一样的。此处就不进行说明

经过上面的分析，代码如下，结合注释和上面的图来说明，比较简单

private String findLongestPalindromeString1(String s) {
            int len = s.length();
            //如果字符串中包含的字符小于1个，可以不需要处理
            if (len < 2) {
                return s;
            }
            //子串的最大长度
            int maxLen = 1;
            //最大回文子串的起始索引
            int begin = 0;
            //定义状态数组
            boolean[][] dp = new boolean[len][len];
            //初始化，当i = j时，表示仅有一个字符，一个字符当然是回文串
            for (int i = 0; i < len; i++) {
                dp[i][i] = true;
            }
    
            //枚举子串长度，这里子串的长度从2开始，
            for (int L = 2; L <= len; L++) {
    
                //枚举左边界
                for (int left = 0; left < len; left++) {
                    //由L 和 left其实是可以确定由边界
                    int right = left + L - 1;
    
                    //如果由边界已经越界了
                    if (right >= len) {
                        break;
                    }
    
                    //如果s[left] != s[right]
                    if (s.charAt(left) != s.charAt(right)) {
                        dp[left][right] = false;
                    } else {
                        //说明字符串的长度等于2，然后s[left] = s[right]，所以dp[left][right] = true
                        if (right - left < 3) {
                            dp[left][right] = true;
                        } else {
                            dp[left][right] = dp[left + 1][right - 1];
                        }
                    }
    
                    if (dp[left][right] && right - left + 1 > maxLen) {
                        maxLen = right - left + 1;
                        begin = left;
                    }
                }
            }
            return s.substring(begin, begin + maxLen);
        }

其实我们可以看出该动态规划的时间复杂度是O(![N^\{2\}][N_2])，空间复杂度也是O(![N^\{2\}][N_2])，我们看到，时间复杂度相对于暴力搜索方法来说已经缩小一个量级，但是空间复杂度却达到了可怕的 O(![N^\{2\}][N_2])。

其实从上面的表格我们也可以看出，左下半部分的空间其实是浪费掉的，对于这种遍历方式，没想到如何优化空间，但是我们可以换一个遍历方式，压缩空间复杂度。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3][]

**动态规划优化一，**其实不能说是优化，只能说从不同的角度去遍历

其实我们可以换一种思路，我们还是以 **abaelele** 作为例子来进行讲解。

状态、状态转移方程和边界条件还是上面的，状态转移方程还是P(i,j)=(P(i+1,j−1)&&S\[i\]==S\[j\])。

想要知道P\[i,x\]。要先知道P\[ i+1,x-1\]。所以我们把i从后往前遍历，但是现在遍历的元素变了，前面一种方法遍历的是子串的长度，现在遍历的直接是左边界。

![20210809204019617.png][]

当左边界确定好之后，再处理右边界就可以了，因为需要知道P\[x,j\]需要先知道P\[x+1，j-1\]。右边界不可能小于左边界，所以右边界从左边界开始，往后遍历。

下面用图进行说明下：

（1）当 i = 7 时，j的取值只能是7，状态如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4][]

（2）当 i = 6时，j 的 取值可以为 6 和 7，当 j 等于6时，因为 i = j，所以dp\[i,j\] = T，当 j = 7时，因为S\[i\] != S\[j\] ，所以dp\[i,j\] = F，如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5][]

（3）当 i = 5 时，j 的 取值可以是5，6，7。当 j 的值是5时，因为 i = j ，所以dp\[i\]\[j\] = T,如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6][]

当 j 的 值是6时，因为S\[i\] != S\[j\]，所以dp\[i\]\[j\] = F，如下图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7][]

接下来比较关键，当 j = 7 时，因为S\[i\] = S\[5\] =S\[j\] = S\[7\] = e。并且dp\[i+1\]\[j-1\] = dp\[6\]\[6\] = T,所以dp\[i\]\[j\] = T，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8][]

（5）其他是类似的，此处不再列举，代码如下。

代码如下

private String findLongestPalindromeString(String s) {
            int n = s.length();
            String res = "";
            //存储已经计算的结果
            boolean[][] dp = new boolean[n][n];
    
            //左边界从后往前遍历
            for (int i = n - 1; i >= 0; i--) {
    
                //右边界从左边界开始，往后遍历
                for (int j = i; j < n; j++) {
                    //如果S[i] != S[j]，S[i~j]不可能是回文串。
                    //如果j-i<2表示i = j，只会有一个字符，一个字符肯定是回文串
                    //如果j-i>=2,且S[i] = S[j],则关注S[i+1 ~ j-1 ]是否是回文串，即dp[i+1][j-1]是否等于true
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || dp[i + 1][j - 1]); //j - i 代表长度减去 1
                    if (dp[i][j] && j - i + 1 > res.length()) {
                        res = s.substring(i, j + 1);
                    }
                }
            }
            return res;
        }

**动态规划的优化二：**针对 *动态规划的优化一，*参见上面，当 i （左边界）从后往前遍历时，右边界（j）采用了从前往后的遍历，那此处我们来看看，右边界 j 能不能从后往前遍历？？我们还是照样以字符串abaelele来进行说明。

（1）当 i=7 ，j 的取值只能是7，得到dp\[i\]\[j\] = T,如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 9][]

（2）当 i = 6 时，j 可以取 6 和 7，我们先看看 j 等于 7的情况，因为 S\[i\] != S\[j\]，所以很自然dp\[i\]\[j\] = F 。 j = 6 时，dp\[i\]\[j\] = T。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 10][]

（3）当i等于5时，问题的关键来了，j 的 取值可以是 5,6,7，我们先看看j等于7的情况。因为有S\[i\] = S\[5\] = S\[j\] = S\[7\] = e。并且 j - i >=2，p\[i\]\[j\] = p\[6\]\[6\] = T。所以为true。如下图

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 11][]

j = 5 和 j = 6的状态类似，处理完后如下图。

（4）看下 i = 4时的情况，j的值可以是4,5,6,7。执行完成后状态如下图，其实只用到了P\[5\]\[5\]的值，与第6和第7其实压根就没有关系了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 12][]

（5）i = 3 ....i = 1的情况其实是类似的。此处不再分析。

根据上面的分析，其实我们可以优化下状态数组，我们其实使用一个一维数组就可以了。代码如下：

private String findLongestPalindromeString(String s) {
            int n = s.length();
            String res = "";
    
            //其实只需要一个一维数组
            boolean[] P = new boolean[n];
    
            for (int i = n - 1; i >= 0; i--) {
                for (int j = n - 1; j >= i; j--) {
                    //计算p[j]，如果s[i] != s[j],则p[j]为false
                    //当s[i] = s[j]时，并且j-i>=2,则我们直接使用左下方的状态就可以。
                    P[j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || P[j - 1]);
                    if (P[j] && j - i + 1 > res.length()) {
                        res = s.substring(i, j + 1);
                    }
                }
            }
            return res;
        }

从前往后遍历时为什么不能使用一维数组，自行使用excel画一个状态转移表就可以知道了，会出现覆盖的情况。

比如 i = 6 和 i = 7 处理之后状态如下，我在下方放了一个一维dp

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 13][]

当i=5时，如果右边界j从前往后遍历，看看会出现的情况。

当j = 5 时，设置dp\[5\]的值没得问题。如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 14][]

j = 6 时，设置dp\[6\]的值为F。但是当j等于7时，计算dp\[7\]，其实dp\[7\]是依赖于左下元素，其实也就是上一个i的状态，但是这里已经把它覆盖掉了。会出现异常。特别是在动态规划过程中，反向遍历是优化很多问题空间复杂度的常用方式。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 15][]

**三、中心扩展算法**

中心扩展算法其实比较好理解，回文串，其实就是根据字符串中心对称的。但是如何找出字符串的中心就比较有技巧  
（1）如果字符串的长度为奇数，如字符串 aba ，则中心就是 字符 b  
（2）如果字符串的长度为偶数，如字符串 abba，则中心 可以理解为 bb 或者 bb之间的空格

知道了中心之后其实就比较简单了，使用两个指针（left 和 right）从中心开始，left向左遍历，right向右遍历，当 S\[left\] != S\[right\]时则终止，代码如下：

private String longestPalindrome(String s) 
    	{
    		if (s.length() < 1)
    		{
    			return "";
    		}
    		int start = 0, end = 0;
    		for (int i = 0; i < s.length(); i++)
    		{
                //一个元素为中心
    			int len1 = expandAroundCenter(s, i, i);
    
                //两个元素为中心
    			int len2 = expandAroundCenter(s, i, i + 1);
    			int len = max(len1, len2);
    			if (len > end - start)
    			{
    				start = i - (len - 1) / 2;
    				end = i + len / 2;
    			}
    		}
    		return s.substr(start, end - start + 1);
    	}
    
    	int expandAroundCenter(string s, int left, int right)
    	{
    		int L = left, R = right;
    		while (L >= 0 && R < s.length() && s[L] == s[R])
    		{// 计算以left和right为中心的回文串长度
    			L--;
    			R++;
    		}
    		return R - L - 1;
    	}

其实中心扩展算法还有一种解法比较巧妙。

可以换一个角度想，中心可以是 n 个字符组成的字符串，只要这n个字符相等即可，比如如下字符串，当前向右遍历到字符b

![20210810135355581.png][]

我们可以定义一个指针left 和 一个 指针right从cur指针开始，left向左走，直到 S\[left\]!=S\[cur\] 或者 left走到字符串左边界。right向右走，直到s\[right\] != s\[cur\] 或者right 走到字符的右边界，状态如下图

![202108101400305.png][]

其实我们可以把 left 与 right的中间部分整体认为是中心。然后left与right再判断是否相等，做同步处理。分析后代码如下：注意下边界的处理，就没啥问题了。

public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) return "";
            int maxBeginIndex = 0;
            int maxLen = 0;
            for (int cur = 0; cur < s.length(); cur++) {
                //当前批次回文串的长度
                int len = 1;
                //定义两个指针从cur开始
                int left = cur-1;
                int right = cur +1 ;
    
                //left一直朝左遍历，直到到达数组左边界或者不等于cur
                while (left >= 0 && s.charAt(left) == s.charAt(cur)) {
                    left--;
                    len++;
                }
    
                //right一直朝右遍历，直到到达数组右边界或者不等于cur
                while (right < s.length() && s.charAt(cur) == s.charAt(right)) {
                    right++;
                    len++;
                }
    
                //判断left处和right处是否相等
                while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                    left--;
                    right++;
                    len = len + 2;
                }
    
                if (len > maxLen) {
                    maxLen = len;
                    maxBeginIndex = left;
                }
            }
    
            return s.substring(maxBeginIndex + 1, maxBeginIndex + maxLen + 1);
        }

**Manacher 算法**

接下来我们看看这种算法，我们以字符串 c a b a d a b a e 进行说明。

前面讲中心扩展算法时，讲过，从左往右遍历，依次把遇到的字符作为中心，然后向左向右扩展，对于遇到的每一个都是这样的操作，其实这中间包含了很多重复的计算操作。

比如我们知道以**第三位**为中心的回文串如下，长度为 **3**

![20210810172959262.png][]

以**第五位**为中心的回文串如下，长度为 **7**

![20210810173143186.png][]

已经知道了 **第3位**（长度为**3**） 和 **第5位**（长度为**7**）为中心的回文串，并且知道了长度。 那此时计算 第 7 位为中心的回文时有哪些已知的信息？接下来详细分析下。

比如以**第5位**为中心的回文串，长度是**7**，由回文串的特性知道，回文串是按照中心成镜像对称的，也就是中心两边的元素个数是相等的，如下图。

![20210810182608950.png][]

中心的右边有多少个元素，左边有多少个元素，其实是可以根据长度确定下来的，比如 中心等于5，长度是7，可以算出中心的右边有 3（7/2向下取整）个元素。左边也是一样的道理

而且根据按中心成镜像对称的特性可知，第 6 位和 第 4 位相等。第 7 位和第 3 位相等。第 8 位 和第 2 位相等。

> 因为2 - 4为是回文串，可以得出6 - 8位也是回文串，所以我们在计算第7位的时候就可以利用到前面的已经计算好的信息，但是我们不知道 第 5 位 和第 9 位是否相等，因为第 9 位根据历史信息是无法得到的。

接下来我们来看看以第 6 位 为中心的回文该怎么计算。

> 由于之前的计算已经知道了第5位为中心的abadaba是回文，因为第 5 位为中心的回文串右边界到第8位，大于第6位，所以可以得出，第 6 位 的元素是等于第 4 位的，而第4位为中心的a的回文长度是1，所以第6位为中心的回文长度只能是1，不用再去扩展判断了。
> 
> 这里为什么确定是1位？
> 
> 因为以第4位为中心的回文长度是1，所以可以得知，第 3 位不等于第 5 位，因为第 3 位等于第 7 位，自然可以得知，第 7 位不等于 第 5位，所以，以第 6 位为中心的回文串的长度只能是1。

从上面的分析可以得知，当我们获得 1 - 5位为中心的回文串，及其回文串的长度时，我们再计算以第6位为中心的回文串时，是可以不需要扩展，而直接根据历史信息获取到，但是计算计算以第7位为中心的回文串时，因为我们目前已知的信息只到第8位，第 9 位是未知信息，所以我们不得不采用遍历的形式继续往两端扩展。

![20210810184722582.png][]

**所以大概的步骤如下：**

1、我们要记录下目前已知的回文串能够覆盖到的最右边的地方，就像案例中的第 8 位  
2、同时，覆盖到最右边的回文串所对应的中心也要记录，就比如案例中的第 5 位  
3、以每一位为中心的回文串的长度也要记录，后面进行推断的时候能用到，就像案例中用到的以第3位为中心的回文和第4位为中心的回文  
4、对于新的中心，我们判断它是否在右边界内，若在，就计算它相对右边界回文中心的对称位置，从而得到一些信息，同时，如果该中心需要进行扩展，则继续扩展就行

**再进行编码之前我们先来思考一个问题：**

1、上面我们所有的假设都是基于中心才有一个元素，但是当偶数时会出现什么情况？如下字符串  
 ***a b b a***  
这种情况我们的算法就会失效，因为此时的中心是两个元素，那其实我们可以加一些出来逻辑，在空格之间加入一个不存在于字符串中的字符，此处以 **\#** 作为不存在的字符为例，处理后，字符串变为了如下：

**\# a \# b \# b \# a \#**

其实这个时候字符串的长度可以为如下：

![20210810185756965.png][]

2、当字符串本就是奇数时会出现什么情况？

***a b a***

其实经过和偶数个时的处理后也是不影响正常结果的，采用 **\#** 处理后变为如下

**\# a \# b \# a \#**

我们看下元素的新中心，如下，还是不影响结果，所以先对字符串处理下。

![2021081019014335.png][]

**最终的处理步骤**

1、先对字符串进行预处理，两个字符之间加上特殊符号\#（不存在于原始字符串中）  
2、然后遍历整个字符串，用一个数组来记录以该字符为中心的回文长度，为了方便计算右边界，我在数组中记录长度的一半（向下取整）  
3、每一次遍历的时候，如果该字符在已知回文串最右边界的覆盖下，那么就计算其相对最右边界回文串中心对称的位置，得出已知回文串的长度  
4、判断该长度和右边界，如果达到了右边界，那么需要进行中心扩展探索。当然，如果第3步该字符没有在最右边界的“羽翼”下，则直接进行中心扩展探索。进行中心扩展探索的时候，同时又更新右边界  
5、最后得到最长回文之后，去掉其中的特殊符号即可。

**接下来我们来看看代码**

预处理字符串代码片段：

private String preHandlerString(String s) {
            StringBuffer sb = new StringBuffer();
            int len = s.length();
            
            //此处用#代替，真正使用时需要用一个不存在于字符串中的字符
            sb.append('#');
            for (int i = 0; i < len; i++) {
                sb.append(s.charAt(i));
                sb.append('#');
            }
            return sb.toString();
        }

最终的代码如下：需要结合前面的解释和注释详细看，当然可参考文末的链接，也许他讲得会清楚很多，但是需要自己列举几个字符串去推敲，走一遍，找规律。

/*
        记住，方法里面的好些注释是根据字符串 c a b a d a b a e进行说明的
        * */
        private String findLongestPalindromeString(String s) {
            //1、先预处理字符串
            String str = preHandlerString(s);
    
            //处理后字符串的长度
            int len = str.length();
    
            //右边界（目前已经算出的回文串所能达到的最右边界，比如 5 的最右边界是 8）
            int rightSide = 0;
    
            //右边界对应的回文中心（就是对应计算出rightSide对应的回文中心，就是5）
            int rightSideCenter = 0;
    
            //保存以每个字符为中心的回文长度一半（向下取整），比如以5为中心的回文长度是7,一半向下取整就是3.
            int[] halfLenArr = new int[len];
    
            //记录回文中心
            int center = 0;
    
            //记录最长的回文长度
            int longestHalf = 0;
    
            for (int i = 0; i < len; i++) {
                //是否需要中心扩展
                boolean needCalc = true;
                
                //如果在右边界覆盖的范围内
                if (rightSide > i) {
                    //计算相对rightSideCenter的对称位置
                    int leftCenter = 2 * rightSideCenter - i;
                    //根据回文性质得到结论
                    halfLenArr[i] = halfLenArr[leftCenter];
                    //如果超过了右边界，进行调整
                    if (i + halfLenArr[i] > rightSide) {
                        halfLenArr[i] = rightSide - i;
                    }
    
                    // 如果根据已知条件计算得出的最长回文小于右边界，则不需要扩展了
                    if (i + halfLenArr[leftCenter] < rightSide) {
                        needCalc = false;
                    }
                }
    
                if (needCalc) {
                    while (i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
                        if (str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
                            halfLenArr[i]++;
                        } else {
                            break;
                        }
                    }
                    // 更新右边界及中心
                    rightSide = i + halfLenArr[i];
                    rightSideCenter = i;
                    // 记录最长回文串
                    if (halfLenArr[i] > longestHalf) {
                        center = i;
                        longestHalf = halfLenArr[i];
                    }
                }
            }
            // 去掉之前添加的#
            StringBuffer sb = new StringBuffer();
            for (int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
                sb.append(str.charAt(i));
            }
            return sb.toString();
        }

参考：[https://mp.weixin.qq.com/s/z8MVwjwqJitzZL13ODTjhA][https_mp.weixin.qq.com_s_z8MVwjwqJitzZL13ODTjhA]

[20210809133826524.png]: /images/20220829/bf49c2ebcd0442e98970ef073ff61868.png
[N_3]: https://latex.codecogs.com/gif.latex?N%5E%7B3%7D
[20210809150526328.png]: /images/20220829/b83fa2e55ea940029fc4d526f6534b5b.png
[20210809151923449.png]: /images/20220829/104cc22284424d93abf491c5eac3b1ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70]: /images/20220829/4fd9ddb0f50b46e28cd82d695327e704.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 1]: /images/20220829/b4e8af2b203643cd9d3d1f79b14b983e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 2]: /images/20220829/5e3cd74cb9c54b90ab51817ca4dbf2a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 3]: /images/20220829/1be7ddef5e594e0f85af46f23858cbac.png
[N_2]: https://latex.codecogs.com/gif.latex?N%5E%7B2%7D
[20210809204019617.png]: /images/20220829/5dfde47a63ec4f68abb8ba0693211878.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 4]: /images/20220829/640d404d02bf4094b16f5f5dcb714799.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 5]: /images/20220829/5367c1f8000d4fb38805ab26987be80b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 6]: /images/20220829/e4427545cd4c4c618352b189886dd8e0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 7]: /images/20220829/b882fafa489a4ebda91aa6adf3ed5550.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 8]: /images/20220829/164747ffe036479fa3eb316035bd6ab7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 9]: /images/20220829/bab375032af9416d91caa7e10b38f062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 10]: /images/20220829/e6b7963fc53945b4bbf6e8bf4a727a17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 11]: /images/20220829/bd662e576cb14ee79f61695f69fce9ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 12]: /images/20220829/9fdcc740b7604ae39fe7360feae0005e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 13]: /images/20220829/04ef13b5b32a4b849fbced3217416450.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 14]: /images/20220829/96f1f542dafb426ab500b1ec8c982e8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljYjE5MTQ4NDU0NTE_size_16_color_FFFFFF_t_70 15]: /images/20220829/bb3404c99b524b5781b87636163cee5c.png
[20210810135355581.png]: /images/20220829/1e0c1eb7494e4421bdd53835854a0135.png
[202108101400305.png]: /images/20220829/c1c204dea7df4255ae1765a83a21ebb5.png
[20210810172959262.png]: /images/20220829/19368a4752e047bbb1f5f6e2548e08ab.png
[20210810173143186.png]: /images/20220829/168f4d74e6c24c7ab7766b9756957521.png
[20210810182608950.png]: /images/20220829/7a1dfb295ceb47eda2fe60b19993dccf.png
[20210810184722582.png]: /images/20220829/1319d32ffae44564968750d943befa40.png
[20210810185756965.png]: /images/20220829/2720301f1e5e4d79b917e24df64e8b6e.png
[2021081019014335.png]: /images/20220829/5f24274c965244229d4233e26cfd04f9.png
[https_mp.weixin.qq.com_s_z8MVwjwqJitzZL13ODTjhA]: https://mp.weixin.qq.com/s/z8MVwjwqJitzZL13ODTjhA