You know what a palindrome is, right?
A palindrome is a phrase or sentence that reads the same forward and backward, such as “Madam, I’m Adam” or “dammit I’m mad” or “a man, a plan, a canal, Panama.”
Longest Palindromic Substring
Computer science goes into the concept of longest palindromic substring, or longest symmetric factor. This is the problem of finding the longest substring of any string that also reads as a palindrome.
Consider the word “bananas” – the “anana” of that is a palindrome. In the word “abracadabra,” the entire word isn’t a palindrome but “aca” and “ada” within that word are palindromic. When taking this approach, it’s sometimes necessary to look at all palindromic substrings that stand alone and can’t be extended or connected to other, longer palindromic substrings.
In the 70s, Glenn Manacher developed an algorithm and set of rules for palindromes that appear at the start of any given string. Later researchers found that this same algorithm can be used to determine all palindromic substrings anywhere in the original input string (both of these are linear time solutions).
Manacher’s Algorithm and Palindrome Function in Java
This algorithm can be considered as a set of ground rules for observations and characteristics of a palindrome and sub-palindrome:
Examples of Palindrome Function in Java
Let’s say that s is a string of N characters. In this case, s2 can be considered a derived string of s, with N * 2 + 1 elements.
Each element should correspond to one or more of the following:
- The N characters in s
- The N-1 boundaries among these characters
- Any boundaries before or after the first and last character
A boundary in s2 can be considered equal to any other boundary in s2, when it comes to matching elements and determining palindromic length. For the array of palindromic span for the elements in s2, from center to either outermost bound, each boundary should be counted toward palindromic length.
In other words, a palindrome that has a palindromic span of 1 would be three elements in length. This would be represented as p in our example.
For the position of the center of the palindrome that includes a boundary closest to the right bound of s2, that will be represented by c in our example, i.e. p*2+1. The position of the rightward boundary of this palindrome will be represented by r, i.e. r = c+p. For the position of a character or boundary in s2 with a palindromic span that has yet to be determined, that should be represented by i in our example, with i always being to the right of c. i2, then, is the mirrored position of i around c, i.e. {i, i2} = {6,4}, {7,3}, {8,2}, when c = 5
Manacher’s Algorithm: Case in Point
char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0; // Here the first element in s2 has been processed.
int m = 0, n = 0; // The walking indices to compare if two elements are the same
for (int i = 1; i<s2.length; i++) {
if (i>r) {
p[i] = 0; m = i-1; n = i+1;
} else {
int i2 = c*2-i;
if (p[i2]<(r-i-1)) {
p[i] = p[i2];
m = -1; // This signals bypassing the while loop below.
} else {
p[i] = r-i;
n = r+1; m = i*2-n;
}
}
while (m>=0 && n<s2.length && s2[m]==s2[n]) {
p[i]++; m--; n++;
}
if ((i+p[i])>r) {
c = i; r = i+p[i];
}
}
int len = 0; c = 0;
for (int i = 1; i<s2.length; i++) {
if (len<p[i]) {
len = p[i]; c = i;
}
}
char[] ss = Arrays.copyOfRange(s2, c-len, c+len+1);
return String.valueOf(removeBoundaries(ss));
}
private static char[] addBoundaries(char[] cs) {
if (cs==null || cs.length==0)
return "||".toCharArray();
char[] cs2 = new char[cs.length*2+1];
for (int i = 0; i<(cs2.length-1); i = i+2) {
cs2[i] = '|';
cs2[i+1] = cs[i/2];
}
cs2[cs2.length-1] = '|';
return cs2;
}
private static char[] removeBoundaries(char[] cs) {
if (cs==null || cs.length<3)
return "".toCharArray();
char[] cs2 = new char[(cs.length-1)/2];
for (int i = 0; i<cs2.length; i++) {
cs2[i] = cs[i*2+1];
}
return cs2;
}
}
Determining If a String is a Palindrome
In these cases, each character can be looped and checked against the character on the opposite side. The problem with this approach is that half the work is unnecessary, as each character is being checked twice.
In the English palindrome “madam,” the algorithm would check each letter as a character, when all that really needs to be compared are the first two characters and last two characters – the middle one would not need to be checked.
Checking for Palindrome String Using Recursion (Courtesy Beginnersbook)
package beginnersbook.com;
import java.util.Scanner;
class PalindromeCheck
{
//My Method to check
public static boolean isPal(String s)
{ // if length is 0 or 1 then String is palindrome
if(s.length() == 0 || s.length() == 1)
return true;
if(s.charAt(0) == s.charAt(s.length()-1))
/* check for first and last char of String:
* if they are same then do the same thing for a substring
* with first and last char removed. and carry on this
* until you string completes or condition fails
* Function calling itself: Recursion
*/
return isPal(s.substring(1, s.length()-1));
/* If program control reaches to this statement it means
* the String is not palindrome hence return false.
*/
return false;
}
public static void main(String[]args)
{
//For capturing user input
Scanner scanner = new Scanner(System.in);
System.out.println("Enter the String for check:");
String string = scanner.nextLine();
/* If function returns true then the string is
* palindrome else not
*/
if(isPal(string))
System.out.println(string + " is a palindrome");
else
System.out.println(string + " is not a palindrome");
}
}
Output 1:
Enter the String for check:
qqaabb
qqaabb is not a palindrome
Output 2:
Enter the String for check:
cocoococ
cocoococ is a palindrome
Some Final Thoughts About Palindrome Function in Java
To sum up, your task with palindromes is to compare characters at the left and right ends of a string. If they don’t match, the string itself isn’t a palindrome. The next step is to compare the two characters that are second to the left and right ends of a string, then continue toward the center of the string or until you find a pair that don’t match.
If you reach the middle of the string, then you do have a palindrome – or at least part of that string can be considered a palindrome. If the string is “madam,” the entire string is a palindrome. If the string is “amadam,” it’s not a palindrome but the “ada” toward the center can be considered as a palindrome.
Leave a Reply