题解 | #最长回文子串#

import java.util.*;

public class Solution { public int getLongestPalindrome(String A) { int len = A.length(); StringBuffer str = new StringBuffer(); for(int i = 0;i < len;i ++){ str.append('#'); str.append(A.charAt(i)); } str.append('#'); char[] ch = str.toString().toCharArray(); int n = ch.length; int[] radius = new int[n]; int mid = 0; int right = 0; int max = 0; for(int i = 0;i < n;i++) { radius[i] = right > i ? Math.min(right - i + 1,radius[2*mid -i]) : 1; while(i + radius[i] < n && i - radius[i] >= 0 && ch[i - radius[i]] == ch[i + radius[i]]){ radius[i] ++; } if(i + radius[i] - 1> right){ right = i + radius[i]-1; mid = i; } max = Math.max(max,radius[i]); } return max -1; // int n = A.length(); // StringBuilder sb = new StringBuilder(); // for(int i = 0;i < n;i++){ // sb.append('#').append(A.charAt(i)); // } // sb.append('#');

// int rmax = 0,mid = 0,ans = 0; // n = n * 2 + 1; // int[] dp = new int[n]; // for(int i = 0;i < n;i++){ // dp[i] = rmax > i ? Math.min(rmax - i + 1,dp[2 * mid - i]) : 1; // while(i + dp[i] < n && i - dp[i] >= 0 && sb.charAt(i + dp[i]) == sb.charAt(i - dp[i])){ // dp[i]++; // }

// if(dp[i] + i - 1 > rmax){ // mid = i; // rmax = i + dp[i] - 1; // }

// ans = Math.max(ans,dp[i]); // }

// return ans - 1; } }