Leetcode:Longest Palindromic Substring之详细分析

原题链接：https://leetcode.com/problems/longest-palindromic-substring/

题目：

翻译：求给定字符串中最长回文串的长度

小序：刚开始看这道题大牛的们的解法时，看不懂（原谅我是个渣渣。。。）后来多看了几篇才明白，觉得应该详细记录说明一下

AC代码：

public class Solution {public String longestPalindrome(String s) {int[] p = new int[2048];//用整型数组来保存trans中以res[i]为中心的回文串长度（单边）//将s中各个字符间插入分隔符，以巧妙得忽略s中字符个数的奇偶差异StringBuilder trans = new StringBuilder("#");//首尾都加额外字符防溢出(实际循环的范围仍是字符串长度，故不影响)for(int i=0; i<s.length(); i++) {trans.append("#");trans.append(s.charAt(i));}trans.append("##");int mx = 0;//保存当前最长回文串的右边界int id = 0;//保存当前最长回文串的对称中心所在位置int end_extend = 0;//保存最终确定的最长回文子串的长度int end_center = 0;//保存最终确定的最长回文子串对称中心在trans中的位置for(int i=1; i<trans.length()-1; i++) {p[i] = mx>i ? Math.min(p[2*id-i], mx-i) : 1;//其中p[2*id-i]是当前位置i关于id对称位置j=2*id-i的p[j].之所以要取二者中较小值是防止当对应p[j]较大时,以i为中心的p[i]会溢出（超过字符串长度）while(trans.charAt(i+p[i]) == trans.charAt(i-p[i])) //循环检查以i为中心，左右对称位置的值（p[i]为半径的值）是否相同，相同则证明回文串长度有p[i]++;if(i+p[i] > mx) { //如果当前回文串的右边界已经超过了上个回文串的右边界，mx = i + p[i]; //则更新回文串右边界长度为当前回文串右边界长度id = i; //同时保存此时的对称中心位置}if(p[i] > end_extend) {end_extend = p[i];end_center = i;}}return s.substring((end_center – end_extend)/2, (end_center -end_extend)/2 + end_extend -1);}} 原理：Manacher’s Alogorithm

利用一个辅助数组

（参考自：）

Manacher部分从位置

刚才只提到部分，，是因为如果

举例说明：

s:cdabadabac

trans:##c#d#a#b#a#d#a#b#a#c##

具体如图：

其实正是p[i]=Math.min(p[2*id-i],mx-i)的原理

欢迎转载学习~

相信优美的生命，就是一曲无字的挽歌，

相关文章：

你感兴趣的文章：

标签云：