1. 回文串

作為程序員，回文串這個詞已經(jīng)見怪不怪了，就是一個字符串正著讀和反著讀是一樣的，形式如abcdcba、bbaabb。這里涉及到奇回文和偶回文，奇回文指回文串的字符數(shù)是奇數(shù)，偶回文指回文串的字符數(shù)是偶數(shù)。前面舉的abcdcba就是奇回文，bbaabb就是偶回文。判斷一個字符串是否是回文串很簡單，只要從字符串的兩端開始往中間掃描，全部匹配成功則是回文串，只要有一次匹配失敗，那么就不是回文串。代碼如下

// 沒有對字符串為null或者空串的返回值進行考慮 static boolean Palindrome(String s){for(int i = 0, j = s.length()-1; i < j; i++, j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true; }

?

2. 最長回文串

在我們了解回文串內(nèi)容后，如果給你一個字符串，你能不能得到該字符串中的最長回文串呢？

2.1 暴力匹配法

最長回文串簡單的解法就是暴力匹配法，依次判斷所有字符數(shù)大于1個的子串是否回文串，并記錄最長的那個回文串。如acbc字符串，得到字符數(shù)大于1的子串a(chǎn)c、cb、bc；acb、cbc；acbc，其中cbc是最長回文串。雖然暴力匹配法思路清晰、代碼簡單，但是如果字符串長度較長時，那么子串的數(shù)量是很龐大的，對于一個長度為n的字符串，它的子串有n(n-1)/2個，加上判斷子串是否為回文串的時間復(fù)雜度是O(n)，所以最終總的時間復(fù)雜度是O(n^3)左右。暴力匹配留給大家自行編寫代碼，博主就偷個懶不寫了。

2.2 中心擴散法

中心擴散法是另一種回文串解決方法，算法思路是從字符串的第一個字符一直遍歷到最后一個字符，每次從該字符往兩邊掃描，如果左右兩邊的值相等，那么往左右兩邊拓展，直至左右兩邊的值不相等或者越界，掃描結(jié)束，記錄此時的左右邊界下標，并且記錄此時的回文串長度。該方法的時間消耗主要是遍歷字符串的每個字符，以及每個字符需要向兩邊拓展擴散，所以總的時間復(fù)雜度為O(n^2)。

圖解：以下以abcfcbd字符串遍歷到 f 字符進行圖解，如下圖。

1. 當(dāng)遍歷abcfcbd字符串的 f 字符時，先令left和right都指向 f 字符。

2. 往左右拓展，可以拓展，left往左移，right往右移

3. 可以拓展，繼續(xù)移動

4. 不可以繼續(xù)拓展，結(jié)束，記錄left和right的位置

?

代碼

public String longestPalindrome(String s) {int len = s.length();if(len <= 1){return s;} int max = 0;int[] index = new int[2];for(int i = 0; i < len-1; i++){// 考慮奇數(shù)回文還是偶數(shù)回文，所以分別計算以i為中心，以i和i+1為中心兩種方式的回文串int[] f1 = findSub(s, i, i);int[] f2 = findSub(s, i, i+1);int f1Len = f1[1] - f1[0];int f2Len = f2[1] - f2[0];// 如果以i為中心的奇回文串長度更長并且大于前面記錄的最大回文串長度max，更新max// 如果以i和i+1為中心的偶回文串長度更長并且大于前面記錄的最大回文串長度max，更新maxif((f1Len > f2Len) && (f1Len > max)){index[0] = f1[0];index[1] = f1[1];max = f1Len;}else if((f1Len <= f2Len) && (f2Len > max)){index[0] = f2[0];index[1] = f2[1];max = f2Len;}}return s.substring(index[0], index[1]+1);}static int[] findSub(String s, int left, int right){// 如果是偶數(shù)回文，left和right不等，需要判斷一下left和right的值是否相等if(s.charAt(left) != s.charAt(right)){return new int[]{left+1, left+1};}while((left >= 0) && (right <= s.length()-1) && (s.charAt(left) == s.charAt(right))){left--;right++;}return new int[]{left+1, right-1};}

?

2.3 Manacher算法?

Manacher算法是一種以O(n)時間復(fù)雜度得到最長回文串的算法，以該算法的發(fā)明者Manacher老先生名字命名。雖然該算法的解釋網(wǎng)上較多，但是有點繁瑣和難懂，博主盡量以自己小白的理解力詳細地進行說明。我們接下來先說說Manacher算法的主要思想，它到底在哪里進行了優(yōu)化？然后我們再上代碼。接下來我們以dcbcdcbca字符串為例，請耐心閱讀。

2.3.1. 對字符串dcbcdcbca先預(yù)處理。

在每個字符兩旁插入分割符，可以是任意字符，因為博主一開始也覺得分隔符不能是字符串中出現(xiàn)的字符，那這里選取'a'字符作為分割符進行證明，預(yù)處理后得到如下字符串str2。

2.3.2. 記錄每個字符的回文半徑

遍歷每個字符時，將每個字符可以向左右兩邊拓展的長度稱為回文半徑，使用val數(shù)組記錄回文半徑。則str2的第1個字符到第13個字符回文半徑數(shù)據(jù)值如下圖所示。

2.3.3 Manacher算法的優(yōu)化之處

其實計算str2的第1個字符到第13個字符回文半徑時Manacher也有優(yōu)化，只是接下來更好講解，所以現(xiàn)在分析。

當(dāng)掃描到str2的第10個字符d時，此時的回文字符串是acabacadacabaca，如下圖所示。

接下來我們要計算str2的第14個字符 b，正常情況下，我們以b為中心向兩邊拓展；Manacher算法的強大就是在此處進行了優(yōu)化。

因為b處在axis和right之間，我們可以看看str2第14個b字符關(guān)于axis對稱的第6個b字符它的回文半徑是多少，為什么可以這樣呢？

接下來看圖解吧，原本以為自己理解了很好描述，但現(xiàn)在發(fā)現(xiàn)自己理解而已，要想描述清楚還是有點難，大家看看圖解吧！

1. 步驟1

?

2. 步驟2

?

3. 步驟3

?

總結(jié)：Manacher算法進行優(yōu)化的部分主要有兩點：①字符串預(yù)處理，添加分割符；②利用回文串的對稱信息，避免重復(fù)計算回文半徑。

看來這種算法還是有些難描述的，大家見諒，還是只能多花點時間去消化，Manacher算法最重要一點就是利用對稱信息。時間復(fù)雜度為啥是O(n)，代碼不僅僅有一個for循環(huán)，而且有while向左右掃描拓展呀？雖然有while，但只有在無法利用對稱信息時才會進入while循環(huán)，所以避免了重復(fù)掃描已掃描過的區(qū)域。

?

代碼

public String longestPalindrome(String s) {int len = s.length();int newLen = 2 * len + 1;// 字符串預(yù)處理，得到填充分隔符后的字符數(shù)組char[] newStr = new char[newLen];for(int i = 0; i < len; i++){newStr[2*i] = 'a';newStr[2*i+1] = s.charAt(i);}newStr[newLen-1] = 'a';// ans是最長回文串的回文半徑，ansIndex是最長回文串的對稱中心int[] val = new int[newLen];int axis = 0;int right = 0;int ans = 0;int ansIndex = 0;for(int i = 0; i < newLen; i++){// 如果當(dāng)前遍歷字符處于回文串的最遠邊界內(nèi)，那么可以利用對稱信息if(i < right){val[i] = Math.min(val[2*axis-i], right-i+1);}else{val[i] = 1;}// 沒有越界，并且回文串向左右拓展成功，那么回文半徑加1while(i-val[i] >= 0 && i+val[i] < newLen && newStr[i-val[i]] == newStr[i+val[i]]){val[i]++;}// 如果當(dāng)前遍歷字符的邊界大于記錄的最遠邊界，更新回文串的最遠邊界if(i+val[i]-1 > right){right = i+val[i]-1;axis = i;}// 記錄最長回文串的回文半徑和對稱中心if(val[i] > ans){ans = val[i];ansIndex = i;}}StringBuilder sb = new StringBuilder();for(int i = ansIndex-ans+1; i < ansIndex+ans-1; i++){sb.append(newStr[++i]);}return sb.toString();}

?

以下是力扣的運行結(jié)果

總結(jié)

以上是生活随笔為你收集整理的通俗易懂的最长回文串图解、说明及Java代码（中心扩散法和Manacher算法）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。