Manacher Algorithm in Java

In this section 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.

In each of the four scenarios, we first set the least for 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 length array, positions, index, symmetry property, and other terms, the above observation might appear more logical, understandable, and simple to apply.

File Name: SVSC.java

// Manacher's Algorithm implementation in Java
import java.util.*;
 
class SVSC
{
    static void findTheLongestPalindromicString(String msg)
    {
        int M = msg.length();
        if (M == 0)
            return;
        M = 2 * M + 1; // It is the Position count
        int[] K = new int[M + 1]; //The LPS Length Array
        K[0] = 0;
        K[1] = 1;
        int D = 1; // ThecenterPosition
        int Q = 2; // ThecenterRightPosition
        int s = 0; //ThecurrentRightPosition
        int sMirror; // ThecurrentLeftPosition
        int themaxLPSLength = 0;
        int themaxLPSCenterPosition = 0;
        int strt = -1;
        int end = -1;
        int dif = -1;
 
        // To output the LPS Length array, remove the comment.
        // printf("%d %d ", K[0], K[1]);
        for (s = 2; s < M; s++)
        {
 
            // obtain the sMirror in thecurrentLeftPosition
            // for thecurrentRightPosition s
            sMirror = 2 * D - s;
            K[s] = 0;
            dif = Q - s;
 
            // If thecurrentRightPosition s is within
            // thecenterRightPosition Q
            if (dif > 0)
                K[s] = Math.min(K[sMirror], dif);
 
   // Expand palindrome with thecurrentRightPosition s as the centre. 
// In this case, for odd places, we compare the characters, 
 // and if a match is found, we increase the LPS Length by the one. 
// If even, we simply increase LPS by one without 
 // conducting a character comparison.
            while (((s + K[s]) + 1 < M && (s - K[s) > 0) &&
                               (((s + K[s] + 1) % 2 == 0) ||
                         (msg.charAt((s + K[s] + 1) / 2) ==
                          msg.charAt((s - K[s] - 1) / 2))))
            {
                K[s]++;
            }
 
            if (K[s] > themaxLPSLength) // Track themaxLPSLength
            {
                themaxLPSLength = K[s];
                themaxLPSCenterPosition = s;
            }
 
 // If the palindrome is centred at thecurrentRightPosition s, 
// it will extend beyond thecenterRightPosition Q, 
// and centerPosition D will be adjusted to reflect this.
            if (s + K[s] > Q)
            {
                D = s;
                Q = s + K[s];
            }
 
            // To output the LPS Length array, remove the comment.
            // printf("%d ", K[s]);
        }
 
        strt = (themaxLPSCenterPosition - themaxLPSLength) / 2;
        end = strt + themaxLPSLength - 1;
        System.out.printf("LPS of the string is %h : ", msg);
        for (s = strt; s <= end; s++)
            System.out.print(msg.charAt(s));
        System.out.println();
    }
 
    // It is the Driver Code
    public static void main(String[] args)
    {
        String msg = "abadabadabddab";
        thefindLongestPalindromicString(msg);
 
        msg = "babbab";
        thefindLongestPalindromicString(msg);
 
        msg = "abababa";
        thefindLongestPalindromicString(msg);
 
        msg = "badabadabadab";
        thefindLongestPalindromicString(msg);
 
        msg = "wolfthesehtwolf";
        thefindLongestPalindromicString(msg);
 
        msg = "dbab";
        thefindLongestPalindromicString(msg);
 
        msg = "abacdfgdcaba";
        thefindLongestPalindromicString(msg);
 
        msg = "abacdgfdcabba";
        thefindLongestPalindromicString(msg);
 
        msg = "abacedecaba";
        thefindLongestPalindromicString(msg);
    }
}

Output:

LPS of the string is abadabadabddab: badabadab
LPS of string is babbab: babbab
LPS of string is abababa: bababab
LPS of string is badabadabadab: badabadabadab
LPS of string is wolftheehtwolf: theeht
LPS of string is dbab: bab
LPS of string is abacdfgdcaba: bab
LPS of string is abacdgfdcabba: baab
LPS of string is abacedecaba: abacedecaba

Time Complexity: O(n)

Auxiliary Space: O(n)

Alternative Methods:

Here, we've covered two strategies. We worked with the provided string in both strategies. Here, we had to compare the characters for expansion while handling even and odd situations differently. We have to ensure even positions also reflect some character in order to prevent this inconsistent treatment of an even odd positions. One technique to accomplish this is to change the given string or make a new duplicate of the given string and place a character in all even spots. As an illustration, if the input text is "abcb," the resulting string should be "#a#b#c#b#" if the # character is added at even locations.

The two methods that have already been mentioned can be slightly changed to operate on modified strings when distinct addressing of an even odd locations is not required.

In order to bypass bound check, we must additionally add 2 DIFFERENT character as sentinels at the beginning and end of the string in the even and odd locations. With these modifications, the string "bada" will appear as "#b#a#d#a#$," with and $ serving as sentinels.

With increased memory usage, this implementation might appear cleaner.

Since it's a straightforward adjustment in the existing implementations, we really aren't implementing these here.