题目描述
给你一个字符串 s,找到 s 中最长的回文子串。
代码
class Solution {
public String longestPalindrome(String s) {
int n = s.length(), k = 0;
char[] a = s.toCharArray(), b = new char[(n<<1)+10];
int[] f = new int[(n<<1)+3]; //f[i]表示以i为中心的最长回文子串半径
b[k++] = '$';
b[k++] = '#';
for(int i=0; i<n; i++){
b[k++] = a[i];
b[k++] = '#';
}
b[k++] = '^';
int mid = 0, mr = 0;
n = n*2+3;
for(int i=1; i<n; i++){
if(i<mr) f[i] = Math.min(f[mid*2-i], mr-i);
else f[i] = 1;
while(b[i-f[i]]==b[i+f[i]]) f[i]++;
if(i+f[i]>mr){
mid = i;
mr = i+f[i];
}
}
int res = 0;
for(int i=0; i<n; i++){
if(res<f[i]){
mid = i;
res = f[i]-1;
}
}
String str = new String(b);
String ans = str.substring(mid-(f[mid]-1), mid+f[mid]-1+1).replace("#", "");
return ans;
}
}