longest plaindrome record java
public class Solution {
public String longestPalindrome(String s) {
//Special Judgment
int len = s.length();
if (len < 2) {
return s;
}
//Get the preprocessed string
String str = addBoundaries(s, '#');
//The length of the new string
int sLen = 2 * len + 1;
//Array p records information about scanned palindrome substrings
int[] p = new int[sLen];
//Double pointers, which correspond to one another and must be updated at the same time
int maxRight = 0;
int center = 0;
//The maximum number of central diffusion steps currently traversed, which is equal to the length of the longest palindrome substring of the original string
int maxLen = 1;
//The starting position of the longest palindrome substring of the original string, which must be updated at the same time as maxLen
int start = 0;
for (int i = 0; i < sLen; i++) {
if (i < maxRight) {
int mirror = 2 * center - i;
//This line of code is the key to the Manacher algorithm and is understood in conjunction with graphics
p[i] = Math.min(maxRight - i, p[mirror]);
}
//The left and right starting points of the next attempt to diffuse, the number of steps that can diffuse is added directly to p[i]
int left = i - (1 + p[i]);
int right = i + (1 + p[i]);
//left >= 0 && right < sLen Guarantees no crossing
//(str.charAt(left) ==str.charAt(right) means that it can be diffused 1 time
while (left >= 0 && right < sLen && str.charAt(left) == str.charAt(right)) {
p[i]++;
left--;
right++;
}
//By the definition of maxRight, it is the largest I + p[i] of the traversed I
//The greater the value of maxRight, the greater the likelihood of entering the above i < maxRight judgment, so that you can reuse the palindrome information you have previously judged
if (i + p[i] > maxRight) {
//The maxRight and center need to be updated at the same time
maxRight = i + p[i];
center = i;
}
if (p[i] > maxLen) {
//Records the length of the longest palindrome substring and its corresponding starting point in the original string
maxLen = p[i];
start = (i - maxLen) / 2;
}
}
return s.substring(start, start + maxLen);
}
/**
* Create Preprocessed String
*
* @param s Original string
* @param divide Separator Character
* @return String resulting from processing with delimiter
*/
private String addBoundaries(String s, char divide) {
int len = s.length();
if (len == 0) {
return "";
}
if (s.indexOf(divide) != -1) {
throw new IllegalArgumentException("Parameter error, the split character you passed exists in the input string!");
}
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < len; i++) {
stringBuilder.append(divide);
stringBuilder.append(s.charAt(i));
}
stringBuilder.append(divide);
return stringBuilder.toString();
}
}