Manachers Algorithm in Java

Here, we'll go over the four scenarios once more in an effort to approach them differently and use the same strategy.

The values of (centerRightPosition - currentRightPosition) and LPS length at currentLeftPosition, respectively, determine the four scenarios (R – i). These two pieces of knowledge allow us to utilise previously acquired data without comparing unneeded characters.

Manacher's Algorithm - Longest Palindromic Substring in Linear Time

In each of the four scenarios, we first set the least of L[iMirror] as well as R-i to L[i], and then we attempt to make the palindrome as long as possible.

Given that one is familiar with the LPS size arrays, position, index, symmetry property, and other terms, the above observation might appear more logical, understandable, and simple to apply.

Execution:

// Manacher's Algorithm implementation program in java
import java.util.*;
class Kamal
{
    static void findTheLongestPalindromicString(String message)
    {
        int M = message.length();
        if (M == 0)
            return;
        M = 2 * M + 1; // The position number
        int[] K = new int[M + 1]; // Length of LPS Array
        K[0] = 0;
        K[1] = 1;
        int D = 1; // The Position at center
        int A = 2; // The position of centerRightPosition
        int j = 0; // The position of currentRightPosition
        int iMirror; // The position of currentLeftPosition
        int themaxLPSLength = 0;
        int themaxLPSCenterPosition = 0;
        int begin = -1;
        int end = -1;
        int differ = -1;
        // To output the LPS Length array, remove the comment.
        // printf("%d %d ", K[0], K[1]);
        for (j = 2; j < M; j++)
        {
            // obtain the currentLeftPosition jMirror and 
           //   use it for the currentRightPosition j.
            jMirror = 2 * D - j;
            K[j] = 0;
            differ = A - j;
 
            // If the currentRightPosition j is well 
            // within the centerRightPosition A
            if (differ > 0)
                K[j] = Math.min(K[jMirror], differ);
 
            // Expand palindrome with currentRightPosition j
          //  as the centre. In this case, for odd places, 
          // we compare the characters, and if a match is found, 
          // we increase the LPS Size by one. If even, 
        // we simply increase LPS by one without 
       // conducting a character comparison.
            while (((j + K[j]) + 1 < M && (j - K[j]) > 0) &&
                               (((j + K[j] + 1) % 2 == 0) ||
                         (message.charAt((j + K[j] + 1) / 2) ==
                          message.charAt((j - K[j] - 1) / 2))))
            {
                K[j]++;
            }
 
            if (K[j] > themaxLPSLength) // Track the themaxLPSLength
            {
                themaxLPSLength = K[j];
                themaxLPSCenterPosition = j;
            }
            // If the palindrome is centred at currentRightPosition j
           //  it will extend beyond centerRightPosition A, 
          // and the centerPosition D will be adjusted in 
           // accordance with the expanded palindrome.
            if (j + K[j] > A)
            {
                D = j;
                A = j + K[j];
            }
            // To output the LPS Length array, remove the comment.
            // printf("%d ", K[j]);
        }
 
        begin = (themaxLPSCenterPosition - themaxLPSLength) / 2;
        end = begin + themaxLPSLength - 1;
        System.out.printf("The LPS for string is %h : ", message);
        for (j = begin; j <= end; j++)
            System.out.print(message.charAt(j));
        System.out.println();
    }
 
    // It is the Driver Code
    public static void main(String[] args)
    {
        String message = "abadabadabddcb";
        findTheLongestPalindromicString(message);
 
        message = "babbab";
        findTheLongestPalindromicString(message);
 
        message = "bababab";
        findTheLongestPalindromicString(message);
 
        message = "badabadabadab";
        findTheLongestPalindromicString(message);
 
        message = "forjavaavajfor";
        findTheLongestPalindromicString(message);
 
        message = "dbab";
        findTheLongestPalindromicString(message);
 
        message = "abacegfecaba";
        findTheLongestPalindromicString(message);
 
        message = "abacegfdcbaab";
        findTheLongestPalindromicString(message);
 
        message = "abcdefedcba";
        findTheLongestPalindromicString(message);
    }
}

Output:

The LPS for string is  abacdabadabddab : badabadab
The LPS for string is  babbab : babbab
The LPS for string is  bababab : bababab
The LPS for string is  badabadabadab : badabadabadab
The LPS for string is  forjavaavajfor : javajava
The LPS for string is  dbab : bab
The LPS for string is  abacegfecaba : aba
The LPS for string is  abacegfdcbaab : baab
The LPS for string is  abcdefedcba : abcdefedcba

Time Complexity of program: O(n)
Auxiliary Space of program: O(n)

When comparing characters for expansion in this case, we had to consider even and odd positions differently (because locations themselves do not correspond to any characters in a string).

Making even positions also represent a character is necessary in order to prevent this inconsistent treatment of even and odd situations (Actually, in character comparison, all even spots should reflect the SAME character). Setting a character to all even spots in the given string or making a fresh duplicate of the given string is one approach to accomplish this.