LeetCode-最长回文子串
这是一道回文串的模板题,我们只要记录回文串的半径和开始的位置就能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);
}
}