Manacher.java

packagecom.thealgorithms.strings;

/**
 * Wikipedia: https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm
 */
publicfinalclassManacher {

privateManacher() {
 }

/**
 * Finds the longest palindromic substring using Manacher's Algorithm
 *
 * @param s The input string
 * @return The longest palindromic substring in {@code s}
 */
publicstaticStringlongestPalindrome(Strings) {
finalStringprocessedString = preprocess(s);
int[] palindromeLengths = newint[processedString.length()];
intcenter = 0;
intrightBoundary = 0;
intmaxLen = 0;
intcenterIndex = 0;

for (inti = 1; i < processedString.length() - 1; i++) {
intmirror = 2 * center - i;

if (i < rightBoundary) {
palindromeLengths[i] = Math.min(rightBoundary - i, palindromeLengths[mirror]);
 }

while (processedString.charAt(i + 1 + palindromeLengths[i]) == processedString.charAt(i - 1 - palindromeLengths[i])) {
palindromeLengths[i]++;
 }

if (i + palindromeLengths[i] > rightBoundary) {
center = i;
rightBoundary = i + palindromeLengths[i];
 }

if (palindromeLengths[i] > maxLen) {
maxLen = palindromeLengths[i];
centerIndex = i;
 }
 }

finalintstart = (centerIndex - maxLen) / 2;
returns.substring(start, start + maxLen);
 }

/**
 * Preprocesses the input string by inserting a special character ('#') between each character
 * and adding '^' at the start and '$' at the end to avoid boundary conditions.
 *
 * @param s The original string
 * @return The preprocessed string with additional characters
 */
privatestaticStringpreprocess(Strings) {
if (s.isEmpty()) {
return"^$";
 }
StringBuildersb = newStringBuilder("^");
for (charc : s.toCharArray()) {
sb.append('#').append(c);
 }
sb.append("#$");
returnsb.toString();
 }
}