Repository: TheAlgorithms/Java (java)

Issue:
[FEATURE REQUEST] <title>Add a new Algorithm Manacher’s Algorithm
### What would you like to Propose?

Here's an algorithm that is not listed in the structure you provided: "Manacher's Algorithm", which is used to find the longest palindromic substring in linear time.

Algorithm: Manacher’s Algorithm
Purpose:
Given a string s, the algorithm finds the longest palindromic substring in linear time (O(n)).


### Issue details

Preprocess the string:

Insert special characters (like #) between each character of the original string and add ^ at the beginning and $ at the end to avoid boundary conditions. This turns any even-length palindrome into an odd-length one.
Example: "abba" becomes "^#a#b#b#a#$".
Initialize Variables:

P[]: An array where P[i] stores the radius of the palindrome centered at position i.
C: The center of the current palindrome.
R: The right boundary of the current palindrome.
Iterate Over the String:

For each character in the transformed string:
Mirror the palindrome from the left side if the current index is within the bounds of the current palindrome.
Try expanding the palindrome centered at the current character.
Update the center C and the right boundary R if the palindrome expands beyond the current boundary.
Return the Result:

The longest palindrome found will be the one with the maximum value in P[]. Use this to find the center and reconstruct the longest palindromic substring from the original string.


### Additional Information

_No response_

Pull request:
Add Manacher’s Algorithm for Longest Palindromic Substring
<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

This PR adds Manacher's Algorithm to find the longest palindromic substring in linear time.

Closes #5453

Patch:
diff --git a/src/main/java/com/thealgorithms/strings/Manacher.java b/src/main/java/com/thealgorithms/strings/Manacher.java
new file mode 100644
index 00000000..34c30382
--- /dev/null
+++ b/src/main/java/com/thealgorithms/strings/Manacher.java
@@ -0,0 +1,69 @@
+package com.thealgorithms.strings;
+
+/**
+ * Wikipedia: https://en.wikipedia.org/wiki/Longest_palindromic_substring#Manacher's_algorithm
+ */
+public final class Manacher {
+
+    private Manacher() {
+    }
+
+    /**
+     * Finds the longest palindromic substring using Manacher's Algorithm
+     *
+     * @param s The input string
+     * @return The longest palindromic substring in {@code s}
+     */
+    public static String longestPalindrome(String s) {
+        final String processedString = preprocess(s);
+        int[] palindromeLengths = new int[processedString.length()];
+        int center = 0;
+        int rightBoundary = 0;
+        int maxLen = 0;
+        int centerIndex = 0;
+
+        for (int i = 1; i < processedString.length() - 1; i++) {
+            int mirror = 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;
+            }
+        }
+
+        final int start = (centerIndex - maxLen) / 2;
+        return s.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
+     */
+    private static String preprocess(String s) {
+        if (s.isEmpty()) {
+            return "^$";
+        }
+        StringBuilder sb = new StringBuilder("^");
+        for (char c : s.toCharArray()) {
+            sb.append('#').append(c);
+        }
+        sb.append("#$");
+        return sb.toString();
+    }
+}


Test patch:
diff --git a/src/test/java/com/thealgorithms/strings/ManacherTest.java b/src/test/java/com/thealgorithms/strings/ManacherTest.java
new file mode 100644
index 00000000..dc74df31
--- /dev/null
+++ b/src/test/java/com/thealgorithms/strings/ManacherTest.java
@@ -0,0 +1,53 @@
+package com.thealgorithms.strings;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
+
+public class ManacherTest {
+
+    @ParameterizedTest
+    @MethodSource("provideTestCasesForLongestPalindrome")
+    public void testLongestPalindrome(String input, String expected) {
+        assertEquals(expected, Manacher.longestPalindrome(input));
+    }
+
+    private static Stream<Arguments> provideTestCasesForLongestPalindrome() {
+        return Stream.of(Arguments.of("abracadabraabcdefggfedcbaabracadabra", "aabcdefggfedcbaa"), Arguments.of("somelongtextwithracecarmiddletext", "racecar"), Arguments.of("bananananananana", "ananananananana"), Arguments.of("qwertydefgfedzxcvbnm", "defgfed"),
+            Arguments.of("abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba", "abcdefghijklmnopqrstuvwxyzzyxwvutsrqponmlkjihgfedcba"));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCasesForEmptyAndSingle")
+    public void testEmptyAndSingle(String input, String expected) {
+        assertEquals(expected, Manacher.longestPalindrome(input));
+    }
+
+    private static Stream<Arguments> provideTestCasesForEmptyAndSingle() {
+        return Stream.of(Arguments.of("", ""), Arguments.of("a", "a"));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCasesForComplexCases")
+    public void testComplexCases(String input, String expected) {
+        assertEquals(expected, Manacher.longestPalindrome(input));
+    }
+
+    private static Stream<Arguments> provideTestCasesForComplexCases() {
+        return Stream.of(Arguments.of("abcdefghijklmnopqrstuvwxyzttattarrattatabcdefghijklmnopqrstuvwxyz", "tattarrattat"), Arguments.of("aaaaabaaaaacbaaaaa", "aaaaabaaaaa"), Arguments.of("sometextrandomabcdefgabcdefghhgfedcbahijklmnopqrstuvwxyz", "abcdefghhgfedcba"),
+            Arguments.of("therewasasignthatsaidmadaminedenimadamitwasthereallalong", "madaminedenimadam"));
+    }
+
+    @ParameterizedTest
+    @MethodSource("provideTestCasesForSentencePalindromes")
+    public void testSentencePalindromes(String input, String expected) {
+        assertEquals(expected, Manacher.longestPalindrome(input));
+    }
+
+    private static Stream<Arguments> provideTestCasesForSentencePalindromes() {
+        return Stream.of(Arguments.of("XThisisalongtextbuthiddeninsideisAmanaplanacanalPanamaWhichweknowisfamous", "lanacanal"), Arguments.of("AverylongstringthatcontainsNeveroddoreveninahiddenmanner", "everoddoreve"));
+    }
+}