Java based O(N) solution using Manacher's algorithm


  • 0

    The description about manacher's algorithm which is the best solution for Longest Palindromic Substring can be found here https://discuss.leetcode.com/topic/80861/java-o-n-solution-based-on-manacher-s-algorithm-faster-than-97-16

    For this solution I am trying to find the longest palindrome starting with the first postion which is done in O(n) time then I take the rest of the string except this palindrome in the original string and append the string to the beginning of the original string.

    public class Solution {
        public String shortestPalindrome(String s) {
            if(s==null||s.length()<=1)
                return s;
            String fromBeingingLongest = longestPalindrome(s);
            StringBuffer toAdd = new StringBuffer(s.substring(fromBeingingLongest.length()));
            return toAdd.reverse().toString()+s;
        }
        public String longestPalindrome(String s) {
            if(s==null||s.length()<=1)
                return s;
            char[] sArray= s.toCharArray();
            char[] s2Array = new char[2*sArray.length+1];
            for(int i=0;i<s2Array.length-1;i+=2){
                s2Array[i]='|';
                s2Array[i+1]=sArray[i/2];
            }
            s2Array[s2Array.length-1]='|';
            int[] dp = new int[s2Array.length];
            int c=0,r=0;
            int m=0,n=0;
            int len = 0, pos = 0;
            for(int i=1;i<s2Array.length;i++){
                if(i>r-1){
                    dp[i]=0;
                    m=i-1;
                    n=i+1;
                }else{
                    int i2=c*2-i;//c-dp[c]+r-i = c-dp[c]+dp[c]+c-i
                    if(dp[i2]+i<r){
                        dp[i]=dp[i2];
                        m=-1;
                    }else {
                        dp[i]=r-i;
                        n = r+1; 
                        m = i*2-n;
                    }
                }
                while(m>=0&&n<s2Array.length&&s2Array[m]==s2Array[n]){
                    dp[i]++;
                    m--;
                    n++;
                }
                if(r<i+dp[i]){
                    c=i;
                    r=i+dp[i];
                }
                if(i>s2Array.length-1 && dp[i]>(s2Array.length-i)/2){
                    break;
                }
            }
            for(int i=0;i<dp.length;i++){
                if(i-dp[i]==0 && len<dp[i]){
                    len=dp[i];
                    pos=i;
                }
            }
            char[] resultTemp = Arrays.copyOfRange(s2Array, pos-len, pos+len+1);
            char[] result = new char[(resultTemp.length-1)/2];
            for (int i = 0; i<result.length; i++) {
                result[i] = resultTemp[i*2+1];
            }
            return String.valueOf(result);
        }
    }
    

Log in to reply
 

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