题解 | #最长回文子串#

import java.util.*;

public class Solution { public int getLongestPalindrome(String A) { 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;
}

}