A palindrome is a word or number which reads same using backward and forward. Write a program to find a maximum-length contiguous substring of a given string that is also a palindrome.
Algorithm Explanation
Initialize the string and pass the string as an argument to the utility function.
Add the Boundaries and find the longest palindrome substring.
Remove the Boundaries.
Return the string and display the palindrome string.
Source Code
package com.dsacode.DataStructre.array;
import java.util.Arrays;
public class LongestPalindrome {
public String findLongestPalindrome(String s) {
if (s==null || s.length()==0)
return "";
char[] s2 = addBoundaries(s.toCharArray());
int[] p = new int[s2.length];
int c = 0, r = 0;
int m = 0, n = 0;
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)) {
p[i] = p[i2];
m = -1;
} 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;
}
public static void main(String[] args) {
String str="aibohphobia eye radar otto";
System.out.println("Palindrome word to find the longest palindrome: " + str);
LongestPalindrome obj = new LongestPalindrome();
System.out.println("Longest palindrome from given string: "+obj.findLongestPalindrome(str));
}
}
Output
Palindrome word to find the longest palindrome: aibohphobia eye radar otto
Longest palindrome from given string: aibohphobia