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

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

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;
}
}
}
}
復(fù)制代碼
當(dāng)然，上面這種算法也有優(yōu)化的空間，基本的思路如下：

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

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

假設(shè)對(duì)于一個(gè)回文串，以及其中心位置，由回文串的性質(zhì)可知，從其中心向兩側(cè)逐步擴(kuò)散到邊界為止，每一步所對(duì)應(yīng)范圍的字串都是回文串

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

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

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

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

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

轉(zhuǎn)換后，所有回文子串的長(zhǎng)度為奇數(shù)，故以中心位置下標(biāo)為 i 的最長(zhǎng)回文串長(zhǎng)度為 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

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

若 i > len[p] + p ，暴力比較 ,通常出現(xiàn)在求取最開(kāi)始時(shí)。
若 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]，此時(shí)，可能存在超出原有 p 的回文區(qū)域，仍需從邊界 i + 1 + len[i] 出發(fā)一一比較

做完當(dāng)前中心 i 的長(zhǎng)度求取之后，判斷是否 i 的回文區(qū)域右邊界大于原有回文右邊界值，若大于，更新中心點(diǎn)為 i ，右邊界為 i 的回文右邊界。
解決 len 數(shù)組的求取問(wèn)題就基本完成對(duì)于 Manachar 算法的理解。相關(guān)代碼如下：
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;
}
// 馬拉車(chē)算法
public static String longestPalindrome(String str) {
String S = preProcess(str);
int n = S.length();// 保留回文串的長(zhǎng)度
int[] len = new int[n];
int center = 0, right = 0;// 保留邊界最右的回文核心以及右邊界
// 從第 1 個(gè)字符開(kāi)始
for (int i = 1; i < n - 1; i++) {
// 找出i對(duì)于后面核心的對(duì)稱(chēng)
int mirror = 2 * center - i;
if (right > i) {
// i 在右邊界的范疇內(nèi)，看看i的對(duì)稱(chēng)點(diǎn)的回文串長(zhǎng)度，以及i到右邊界的長(zhǎng)度，取兩個(gè)較小的那個(gè)
// 不能溢出之前的邊界，否則就得核心拓展
len[i] = Math.min(right - i, len[mirror]);
} else {
// 超過(guò)范疇了，核心拓展
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];
}

}

// 通過(guò)回文長(zhǎng)度數(shù)組找出最長(zhǎng)的回文串
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);
}


審核編輯：湯梓紅