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.