# 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)
{
findTheLongestPalindromicString(message);

message = "babbab";
findTheLongestPalindromicString(message);

message = "bababab";
findTheLongestPalindromicString(message);

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