214. 最短回文串

難度困難114

給定一個字符串?s，你可以通過在字符串前面添加字符將其轉換為回文串。找到并返回可以用這種方式轉換的最短回文串。

示例?1:

輸入: "aacecaaa"
輸出: "aaacecaaa"

示例 2:

輸入: "abcd"
輸出: "dcbabcd"

思路：馬拉車求出以0開頭的最大回文串，然后在前面添加后面字符串的翻轉即可。

傻子都能看懂的馬拉車Manacher

class Solution {
public String preProcess(String s) {int n = s.length();if (n == 0) {return "^$";}String ret = "^";for (int i = 0; i < n; i++)ret += "#" + s.charAt(i);ret += "#$";return ret;
}// 馬拉車算法
public String shortestPalindrome(String s) {String T = preProcess(s);int n = T.length();int[] P = new int[n];int C = 0, R = 0;for (int i = 1; i < n - 1; i++) {int i_mirror = 2 * C - i;if (R > i) {P[i] = Math.min(R - i, P[i_mirror]);// 防止超出 R} else {P[i] = 0;// 等于 R 的情況}// 碰到之前講的三種情況時候，需要利用中心擴展法while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {P[i]++;}// 判斷是否需要更新 Rif (i + P[i] > R) {C = i;R = i + P[i];}}//這里的話需要修改int maxLen = 0;int centerIndex = 0;for (int i = 1; i < n - 1; i++) {int start = (i - P[i]) / 2;//我們要判斷當前回文串是不是開頭是不是從 0 開始的if (start == 0) {maxLen = P[i] > maxLen ? P[i] : maxLen;}}return new StringBuilder(s.substring(maxLen)).reverse() + s;
}
}

?