1 month, 2 weeks

Manacher’s Algorithm




 

Manacher's algorithm is used to find the longest palindromic substring in linear time. It is required to solve sub-problems of some very hard problems. The problem statement it solves is: Given a string 's' with the length of 'n'. Find the longest palindromic substring in the given string. A string is a palindrome when it is equal to the reverse of itself.

Brute Force Approach
The brute force / naive approach is slower than Manacher's algorithm, which is to check each substring of the given string whether the substring is a palindrome or not. To do this first, run three nested loops, the outer two loops pick all substrings one by one by fixing the corner characters, the inner loop checks whether the picked substring is palindrome or not. 

def printSubStr(str, low, high):                                                                  
    for i in range(low, high + 1):                                                                  
        print(str[i], end = "")                                                                           

def longestPalSubstr(str):                                                                      
     n = len(str)                                                                                        
     maxLength = 1                                                                                 
     start = 0                                                                                           
     for i in range(n):                                                                                
         for j in range(i, n):                                                                         
             flag = 1                                                                                     
             for k in range(0, ((j - i) // 2) + 1):                                               
                if (str[i + k] != str[j - k]):                                                           
                    flag = 0                                                                              
            if (flag != 0 and (j - i + 1) > maxLength):                                   
                start = i                                                                                
                maxLength = j - i + 1                                                             
     print("Longest palindrome subString is: ", end = "")                        
     printSubStr(str, start, start + maxLength - 1)                                   
     return maxLength                                                                            

In the brute force approach, three nested loops are used to find the longest palindromic substring, so the time complexity will be O(N^3).
No extra space is needed in this approach, so the space complexity will be O(1).

 

Dynamic Programming                                                                                        

The time complexity can be reduced by storing results of sub-problems. To solve this, we maintain a 2D array palindrom[i][j] which is set to true if the substring s(i,j) is a palindrome, otherwise, it is set to false.

def longestPalSubstr(st) :                                                              
    n = len(st)                                                                                  
    table = [[0 for x in range(n)] for y in range(n)]                           
    maxLength = 1                                                                         
    i = 0                                                                                           
    while (i < n) :                                                                             
        table[i][i] = True                                                                     
        i += 1                                                                                     
    start = 0                                                                                        
    i = 0                                                                                            
    while i < n - 1 :                                                                         
        if (st[i] == st[i + 1]) :                                                               
            table[i][i + 1] = True                                                           
            start = i                                                                               
            maxLength = 2                                                                   
        i +=  1                                                                                   
    k = 3                                                                                               
    while k <= n :                                                                                
        i = 0                                                                                       
        while i < (n - k + 1) :                                                               
            j = i + k - 1                                                                        
            if (table[i + 1][j - 1] and st[i] == st[j]) :                               
                table[i][j] = True                                                         
                if (k > maxLength) :                                                   
                    start = i                                                                 
                    maxLength = k                                                     
            i +=  1                                                                         
        k = k + 1                                                                        
    return maxLength                                                              

Time complexity: O(n^2). Two nested traversals are needed.
Auxiliary Space: O(n^2). Matrix of size n*n is needed to store the dp array.

 

Manacher’s algorithm                                                                                                    

Manacher's algorithm is designed to find the palindromic substrings with odd lengths only. 

centerPosition – This is the position for which LPS length is calculated and let’s say LPS length at centerPosition is d (i.e. L[centerPosition] = d)
centerRightPosition – This is the position which is right to the centerPosition and d position away from centerPosition (i.e. centerRightPosition = centerPosition + d)
centerLeftPosition – This is the position which is left to the centerPosition and d position away from centerPosition (i.e. centerLeftPosition = centerPosition – d)
currentRightPosition – This is the position which is right of the centerPosition for which LPS length is not yet known and has to be calculated
currentLeftPosition – This is the position on the left side of centerPosition which corresponds to the currentRightPosition
centerPosition – currentLeftPosition = currentRightPosition – centerPosition
currentLeftPosition = 2* centerPosition – currentRightPosition
i-left palindrome – The palindrome i positions left of centerPosition, i.e. at currentLeftPosition
i-right palindrome – The palindrome i positions right of centerPosition, i.e. at currentRightPosition
center palindrome – The palindrome at centerPosition

def findLongestPalindromicString(text):                                                                       
    N = len(text)                                                                                                              
    if N == 0:                                                                                                                   
        return                                                                                                                     
    N = 2*N+1                   # Position count                                                                    
    L = [0] * N                                                                                                                   
    L[0] = 0                                                                                                                       
    L[1] = 1                                                                                                                      
    C = 1                       # centerPosition                                                                        
    R = 2                       # centerRightPosition                                                                    
    i = 0                       # currentRightPosition                                                                   
    iMirror = 0                 # currentLeftPosition                                                                     
    maxLPSLength = 0                                                                                                     
    maxLPSCenterPosition = 0                                                                                           
    start = -1                                                                                                                          
    end = -1                                                                                                               
    diff = -1                                                                                                                   
    for i in range(2,N):                                                                                                     
        # get currentLeftPosition iMirror for currentRightPosition i
        iMirror = 2*C-i                                                                                                       
        L[i] = 0                                                                                                                
        diff = R - i                                                                                                 
        # If currentRightPosition i is within centerRightPosition R                         
        if diff > 0:                                                                                                    
            L[i] = min(L[iMirror], diff)                                                                             
        # Attempt to expand palindrome centered at currentRightPosition i
        # Here for odd positions, we compare characters and
        # if match then increment LPS Length by ONE
        # If even position, we just increment LPS by ONE without
        # any character comparison
        try:                                                                                                                   
            while ((i+L[i]) < N and (i-L[i]) > 0) and (((i+L[i]+1) % 2 == 0) or     \    

                (text[(i+L[i]+1)//2] == text[(i-L[i]-1)//2])):                      
                L[i]+=1                                                                                              
        except Exception as e:                                                                                 
            pass                                                                                                  
        if L[i] > maxLPSLength:        # Track maxLPSLength                                     
            maxLPSLength = L[i]                                                      
            maxLPSCenterPosition = i                                                         
        # If palindrome centered at currentRightPosition i                                       
        # expand beyond centerRightPosition R,                                                      
        # adjust centerPosition C based on expanded palindrome.                          
        if i + L[i] > R:                                                                                                     
            C = i                                                                                                               
            R = i + L[i]                                                                                                    
    # Uncomment it to print LPS Length array                                                        
    # printf("%d ", L[i]);                                                                                                 
    start = (maxLPSCenterPosition - maxLPSLength) // 2                                              
    end = start + maxLPSLength - 1                                                                                   
    print ("LPS of string is " + text + " : ",text[start:end+1])                                                       


Analysing the Time and Spatial complexity of Manacher's algorithm (N here is the number of characters inside the given string):
The whole string is palindrome around the center position. If we need to calculate Longest Palindromic Substring at each 2*N+1 positions from left to right, then palindrome's symmetric property could help to avoid some of the unnecessary computations. Hence, the time complexity of Manacher's algorithm will be  O(N).
We need O(n) space to create and form p (palindrome width).

 


Responses(0)







Related