word文檔解密方法，【徽信；sjk6070】當我們求取最長回文子串時，常見的方法就是中心擴散法，即從字符中心出發(fā)，向兩邊對比，檢查是否相等，若等于，則繼續(xù)檢查，并使當前字符中心對應的最長回文子串長度加一，否則，結束該字符中心的回文檢查，比較與當前整個字符串的最長回文子串，考慮是否更新整個字符串的最長回文子串長度，繼續(xù)進行下一個字符的判斷。

這種方法的時間復雜度仍為 O(n2)O(n^2)O(n2) ，較普通的暴力破解的方法有著不錯的優(yōu)化，但也不是最佳的思路，相關的代碼如下：

public class Solution {
private int max = 0;
private String res = “”;
public String longestPalindrome(String s) {
if (s.length() == 1) { return s; }
for (int i = 0; i < s.length()-1; i++) {
checkPalindromeExpand(s,i,i);
checkPalindromeExpand(s,i,i+1);
}
return res;
}
public void checkPalindromeExpand(String s, int low, int high) {
while (low >= 0 && high < s.length()) {
if (s.charAt(low) == s.charAt(high)) {
if (high - low + 1 > max) {
max = high - low + 1;
res = s.substring(low,high+1);
}
low–; high++;
} else {
return;
}
}
}
}
復制代碼
當然，上面這種算法也有優(yōu)化的空間，基本的思路如下：

統(tǒng)計字符出現(xiàn)頻率，用數(shù)組表示出現(xiàn)頻率，當某個字符出現(xiàn)頻率為 1 時，認為該字符可能為某段回文子串的中心點，否則，就不屬于任何一個回文子串
找出頻度為1的字符a，看以a為單核中心向外擴散，求最長回文；如果沒有回文，就將它從串中斷開，進行分治；如果回文長度超過記錄，就保存它
然后從左到右查回文，只有長度超過記錄，才保存
第一次串分割完畢后，進行分治，重新統(tǒng)計頻度，回到1步驟

實現(xiàn)代碼可以借鑒：小馬哥最長回文子串長度求取
Manachar算法
求取最長回文子串的長度的最佳方法為 Manachar算法 ，俗稱馬拉車算法。在了解這個算法之前，我們必須先理解回文子串的一些性質：

假設對于一個回文串，以及其中心位置，由回文串的性質可知，從其中心向兩側逐步擴散到邊界為止，每一步所對應范圍的字串都是回文串

如果我們已知一個回文串的中心點 mid 與其邊界范圍。那么，在大多數(shù)情況下，位于邊界內且關于此中心點對稱的兩點a、b，如果有回文串以 a 為中心，那么以 b 為中心的回文串與以 a 為中心的回文串完全相同。并且，它們之間存在這樣的關系：b=2×mid?ab = 2 \times mid - ab=2×mid?a

回文串末尾位置到回文串中心位置的字符長度為該回文串的半徑，若末尾位置的下標為 a ，中心位置的下標為 id ，回文串長度半徑為 len ，即半徑為 len 則它們存在如下關系：
a=id+len÷2a = id + len\div2a=id+len÷2
頭尾添加一個非 * 的特殊符號保證不越界，避免多次判斷是否越界。

為方便處理，將字符串長度可能為奇數(shù)，可能為偶數(shù)的兩種情況進行合并，即在每個字符的左右都加上一個特殊字符，比如 “?*?”。防止越界情況的出現(xiàn)，在開頭添加一個 “@”可看如下實踐：

從以上實踐可得出，由于插入的 # 號的個數(shù)必定等于字符個數(shù)加一再加上 兩個@ 字符，所以總長度是偶數(shù)+奇數(shù)=奇數(shù)，通過這種方法，可以將字符串的長度都化為奇數(shù)，這樣就不需要對長度奇偶性進行分情況討論。
對字符串完成預處理之后，定義一個數(shù)組 len 存入字符串的每個字符作為回文串中心擴散的回文子串長度且為去掉特殊字符的原字符串的總長。

最長回文子串長度：len[i]?1最長回文子串長度：len[i]-1最長回文子串長度：len[i]?1
證明方法如下：

轉換后，所有回文子串的長度為奇數(shù)，故以中心位置下標為 i 的最長回文串長度為 2×len[i]?12 \times len[i] - 12×len[i]?1
在回文串中，特殊字符數(shù)為 len[i] ，而除去特殊字符數(shù)剩下的就為原字符數(shù)，即 (2×len[i]?1)?len[i]=len[i]?1(2\times len[i]-1)- len[i] = len[i] -1(2×len[i]?1)?len[i]=len[i]?1

問題就轉換為了求取 len[i] 中所有的數(shù)。
已知 P 的最長回文子串長度 len[p]，則回文串左邊界為 p - len[p]，右邊界為 p + len[p]
假設在已知中心 p 的左邊有一點 j ，其對稱點為 i，

若 i > len[p] + p ，暴力比較 ,通常出現(xiàn)在求取最開始時。
若 i < len[p] + p ,且 len[j] < len[p] + p - i (右邊界到 i 的距離)，則他被完全包裹入以 p 為中心的子串中，必有 len[i] = len[j]
若 i = len[p] + p ,且 len[j] >= len[p] + p - i ， len[i] = len[j]，此時，可能存在超出原有 p 的回文區(qū)域，仍需從邊界 i + 1 + len[i] 出發(fā)一一比較

做完當前中心 i 的長度求取之后，判斷是否 i 的回文區(qū)域右邊界大于原有回文右邊界值，若大于，更新中心點為 i ，右邊界為 i 的回文右邊界。
解決 len 數(shù)組的求取問題就基本完成對于 Manachar 算法的理解。相關代碼如下：
import java.util.Scanner;

public class Manacher {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.next();
String res = longestPalindrome(str);
System.out.println(res + ": " + res.length());
}
//插入字符
public static String preProcess(String s) {
int n = s.length();
if (n == 0) {
return “^KaTeX parse error: Expected 'EOF', got '}' at position 12: "; }? String…”;
return ret;
}
// 馬拉車算法
public static String longestPalindrome(String str) {
String S = preProcess(str);
int n = S.length();// 保留回文串的長度
int[] len = new int[n];
int center = 0, right = 0;// 保留邊界最右的回文核心以及右邊界
// 從第 1 個字符開始
for (int i = 1; i < n - 1; i++) {
// 找出i對于后面核心的對稱
int mirror = 2 * center - i;
if (right > i) {
// i 在右邊界的范疇內，看看i的對稱點的回文串長度，以及i到右邊界的長度，取兩個較小的那個
// 不能溢出之前的邊界，否則就得核心拓展
len[i] = Math.min(right - i, len[mirror]);
} else {
// 超過范疇了，核心拓展
len[i] = 0;
}

// 核心拓展
while (S.charAt(i + 1 + len[i]) == S.charAt(i - 1 - len[i])) {
len[i]++;
}

// 看看新的索引是不是比之前保留的最右邊界的回文串還要靠右
if (i + len[i] > right) {
// 更新核心
center = i;
// 更新右邊界
right = i + len[i];
}

}

// 通過回文長度數(shù)組找出最長的回文串
int maxLen = 0;
int centerIndex = 0;
for (int i = 1; i < n - 1; i++) {
if (len[i] > maxLen) {
maxLen = len[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2;
return str.substring(start, start + maxLen);
}


審核編輯：湯梓紅