题意：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
题解：这道题很简单，数据量只有1000，所以可以直接暴力。但是我们要考虑大数据的情况，复杂度是O(n^2)肯定过不了。Manacher(马拉车算法)可以在O(n)复杂度查找最长回文串。
关于Manacher算法，可以参考这篇博客https://www.cnblogs.com/cloudplankroader/p/10988844.html
这是一道回文串的模板题，我们只要记录回文串的半径和开始的位置就能AC。
class Solution {
public String longestPalindrome(String s) {
int n = s.length();
String tempStr = "#";
for(int i = 0; i < n; i++){
tempStr += s.charAt(i)+"#";
}
int MX = 0, pos = 0, ans = 0, P[] = new int[2*n +1], reIndex = 0;
for(int i = 0; i < tempStr.length(); i++){
if(i >= MX){
P[i] = 1;
}else{
P[i] = Math.min(P[2*pos-i], MX-i);
}
while((i - P[i] >= 0 && i+P[i] < tempStr.length()) &&tempStr.charAt(i+P[i])== tempStr.charAt(i-P[i])){
P[i]++;
}
if(P[i] > ans){
ans = P[i];
reIndex = i;
}
if(MX < P[i] + i){
MX = P[i] + i;
pos = i;
}
}
return s.substring((reIndex- ans +1)/2, (reIndex+ans)/2);
}
}