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


  • 0
    W

    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()+"\"");
         }
    }

Log in to reply
 

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