# Rectify Manacher's Algorithm -- Please vote for wikipedia publishing

• One problem with Manacher's algorithm is that it needs to mock the original string with a distinct character, thus preventing the input string from including that character. A rectification is to identify the longest palindromes along the way with the sum of two end points instead of the center point. The result is still linear.

``````/**/
public class NewAlgorithm {

String s;
int N;
int pl_sum[];
int max_sum=0;
int max_pl=0;
int max_sum_z=0;
int max_pl_z=0;

public NewAlgorithm(String s){
init(s);
}

public void init(String s){
this.s=s;
N=s.length();
pl_sum=new int[2*N];
max_pl=max_sum=0;
}

public String lp() {
run_lp();
int left = (max_sum-max_pl+1)/2;
return s.substring(left, max_pl+left);
}
public void run_lp(){
if(s == null)return;

int n=0;								// end points' sum being considered
int c=-1;								// end points' sum with r just outside at right hand
int r=0;								// the smallest end point outside the right side of longest palindrome identified by c
while (r<N) {
int m = 2*c-n;					  // mirror end points' sum of n relative to longest palindrome of the endpoints' sum c
int cp = (m-pl(m)+1)/2;   // left end point of longest palindrome of the endpoints' sum m
if (cp>c-r+1)					 // c-r+1 is the left end point of longest palendrome of the endpoints' sum c
pl_sum[n]=pl(m);     // pl(i) is pl_sum[i] with sentinels
else{
pl_sum[n]=m-2*(c-r+1)+1;
while (compare(n-r, r)){
pl_sum[n] += 2;
r++;
c=n;
}
if (max_pl<pl_sum[n]){
max_pl=pl_sum[n];
max_sum=n;
int left = (max_sum-max_pl+1)/2;
if(left==0){
max_sum_z=max_sum;
max_pl_z=max_pl;
}
}
}
//System.out.println("--> "+n+" "+pl_sum[n]);
n++;
}
}

private boolean compare(int i1, int i2) {
if(i1<0 || i2>=N) return false;
return s.charAt(i1)==s.charAt(i2);
}

private int pl(int i){
if (i==-1) return 0;
if (i==-2) return 1;
return pl_sum[i];
}

public String spl(){
String prefix="";
for(int i=max_pl_z; i<N; i++){
prefix = s.charAt(i) + prefix;
}
return prefix+s;
}

public static void main(String[]args){
String s;
NewAlgorithm LP;
s="abcd\$\$dcba";
LP=new NewAlgorithm(s);
System.out.println("Find Longest Palindrome in \""+s+"\" with length "+s.length());
System.out.println("\""+LP.lp()+"\"");
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.