In Manacher's Algorithm - Part 1 , we gone through some of the basics and LPS length array. Here we will see how to calculate LPS length array efficiently.
To calculate LPS array efficiently, we need to understand how LPS length for any position may relate to LPS length value of any previous already calculated position. For string “abaaba”, we see following:
If we look around position 3:
- LPS length value at position 2 and position 4 are same
- LPS length value at position 1 and position 5 are same
We calculate LPS length values from left to right starting from position 0, so we can see if we already know LPS length values at positions 1, 2 and 3 already then we may not need to calculate LPS length at positions 4 and 5 because they are equal to LPS length values at corresponding positions on left side of position 3. If we look around position 6:
- LPS length value at position 5 and position 7 are same
- LPS length value at position 4 and position 8 are same
............. and so on. If we already know LPS length values at positions 1, 2, 3, 4, 5 and 6 already then we may not need to calculate LPS length at positions 7, 8, 9, 10 and 11 because they are equal to LPS length values at corresponding positions on left side of position 6. For string “abababa”, we see following:
If we already know LPS length values at positions 1, 2, 3, 4, 5, 6 and 7 already then we may not need to calculate LPS length at positions 8, 9, 10, 11, 12 and 13 because they are equal to LPS length values at corresponding positions on left side of position 7. Can you see why LPS length values are symmetric around positions 3, 6, 9 in string “abaaba”? That’s because there is a palindromic substring around these positions. Same is the case in string “abababa” around position 7. Is it always true that LPS length values around at palindromic center position are always symmetric (same)? Answer is NO. Look at positions 3 and 11 in string “abababa”. Both positions have LPS length 3. Immediate left and right positions are symmetric (with value 0), but not the next one. Positions 1 and 5 (around position 3) are not symmetric. Similarly, positions 9 and 13 (around position 11) are not symmetric. At this point, we can see that if there is a palindrome in a string centered at some position, then LPS length values around the center position may or may not be symmetric depending on some situation. If we can identify the situation when left and right positions WILL BE SYMMETRIC around the center position, we NEED NOT calculate LPS length of the right position because it will be exactly same as LPS value of corresponding position on the left side which is already known. And this fact where we are avoiding LPS length computation at few positions makes Manacher's Algorithm linear. In situations when left and right positions WILL NOT BE SYMMETRIC around the center position, we compare characters in left and right side to find palindrome, but here also algorithm tries to avoid certain no of comparisons. We will see all these scenarios soon. Let’s introduce few terms to proceed further:
- 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 – centerPositioncurrentLeftPosition = 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
When we are at centerPosition for which LPS length is known, then we also know LPS length of all positions smaller than centerPosition. Let’s say LPS length at centerPosition is d, i.e. L[centerPosition] = d It means that substring between positions “centerPosition-d” to “centerPosition+d” is a palindrom. Now we proceed further to calculate LPS length of positions greater than centerPosition. Let’s say we are at currentRightPosition ( > centerPosition) where we need to find LPS length. For this we look at LPS length of currentLeftPosition which is already calculated. If LPS length of currentLeftPosition is less than “centerRightPosition – currentRightPosition”, then LPS length of currentRightPosition will be equal to LPS length of currentLeftPosition. So L[currentRightPosition] = L[currentLeftPosition] if L[currentLeftPosition] < centerRightPosition – currentRightPosition. This is
Case 1
Let’s consider below scenario for string “abababa”:
We have calculated LPS length up-to position 7 where L[7] = 7, if we consider position 7 as centerPosition, then centerLeftPosition will be 0 and centerRightPosition will be 14. Now we need to calculate LPS length of other positions on the right of centerPosition. For currentRightPosition = 8, currentLeftPosition is 6 and L[currentLeftPosition] = 0 Also centerRightPosition – currentRightPosition = 14 – 8 = 6 Case 1 applies here and so L[currentRightPosition] = L[8] = 0 Case 1 applies to positions 10 and 12, so, L[10] = L[4] = 0 L[12] = L[2] = 0 If we look at position 9, then: currentRightPosition = 9 currentLeftPosition = 2* centerPosition - currentRightPosition = 2*7 – 9 = 5 centerRightPosition – currentRightPosition = 14 – 9 = 5 Here L[currentLeftPosition] = centerRightPosition – currentRightPosition, so Case 1 doesn’t apply here. Also note that centerRightPosition is the extreme end position of the string. That means center palindrome is suffix of input string. In that case, L[currentRightPosition] = L[currentLeftPosition]. This is
Case 2
. Case 2 applies to positions 9, 11, 13 and 14, so: L[9] = L[5] = 5 L[11] = L[3] = 3 L[13] = L[1] = 1 L[14] = L[0] = 0 What is really happening in Case 1 and Case 2? This is just utilizing the palindromic symmetric property and without any character match, it is finding LPS length of new positions. When a bigger length palindrome contains a smaller length palindrome centered at left side of it’s own center, then based on symmetric property, there will be another same smaller palindrome centered on the right of bigger palindrome center. If left side smaller palindrome is not prefix of bigger palindrome, then
Case 1
applies and if it is a prefix AND bigger palindrome is suffix of the input string itself, then
Case 2
applies.
The longest palindrome i places to the right of the current center (the i-right palindrome) is as long as the longest palindrome i places to the left of the current center (the i-left palindrome) if the i-left palindrome is completely contained in the longest palindrome around the current center (the center palindrome) and the i-left palindrome is not a prefix of the center palindrome (
Case 1
) or (i.e. when i-left palindrome is a prefix of center palindrome) if the center palindrome is a suffix of the entire string (
Case 2
).
In Case 1 and Case 2, i-right palindrome can’t expand more than corresponding i-left palindrome (can you visualize why it can’t expand more?), and so LPS length of i-right palindrome is exactly same as LPS length of i-left palindrome. Here both i-left and i-right palindromes are completely contained in center palindrome (i.e. L[currentLeftPosition] <= centerRightPosition – currentRightPosition) Now if i-left palindrome is not a prefix of center palindrome (L[currentLeftPosition] < centerRightPosition – currentRightPosition), that means that i-left palindrome was not able to expand up-to position centerLeftPosition. If we look at following with centerPosition = 11, then
centerLeftPosition would be 11 - 9 = 2, and centerRightPosition would be 11 + 9 = 20 If we take currentRightPosition = 15, it’s currentLeftPosition is 7. Case 1 applies here and so L[15] = 3. i-left palindrome at position 7 is “bab” which is completely contained in center palindrome at position 11 (which is "dbabcbabd"). We can see that i-right palindrome (at position 15) can’t expand more than i-left palindrome (at position 7). If there was a possibility of expansion, i-left palindrome could have expanded itself more already. But there is no such possibility as i-left palindrome is prefix of center palindrome. So due to symmetry property, i-right palindrome will be exactly same as i-left palindrome and it can't expand more. This makes L[currentRightPosition] = L[currentLeftPosition] in Case 1. Now if we consider centerPosition = 19, then centerLeftPosition = 12 and centerRightPosition = 26 If we take currentRightPosition = 23, it’s currentLeftPosition is 15. Case 2 applies here and so L[23] = 3. i-left palindrome at position 15 is “bab” which is completely contained in center palindrome at position 19 (which is "babdbab"). In Case 2, where i-left palindrome is prefix of center palindrome, i-right palindrome can’t expand more than length of i-left palindrome because center palindrome is suffix of input string so there are no more character left to compare and expand. This makes L[currentRightPosition] = L[currentLeftPosition] in Case 2.
Case 1:
L[currentRightPosition] = L[currentLeftPosition] applies when:
- i-left palindrome is completely contained in center palindrome
- i-left palindrome is NOT a prefix of center palindrome
Both above conditions are satisfied when L[currentLeftPosition] < centerRightPosition – currentRightPosition
Case 2:
L[currentRightPosition] = L[currentLeftPosition] applies when:
- i-left palindrome is prefix of center palindrome (means completely contained also)
- center palindrome is suffix of input string
Above conditions are satisfied when L[currentLeftPosition] = centerRightPosition – currentRightPosition (For 1
st
condition) AND centerRightPosition = 2*N where N is input string length N (For 2
nd
condition).
Case 3:
L[currentRightPosition] > = L[currentLeftPosition] applies when:
- i-left palindrome is prefix of center palindrome (and so i-left palindrome is completely contained in center palindrome)
- center palindrome is NOT suffix of input string
Above conditions are satisfied when L[currentLeftPosition] = centerRightPosition – currentRightPosition (For 1
st
condition) AND centerRightPosition < 2*N where N is input string length N (For 2
nd
condition). In this case, there is a possibility of i-right palindrome expansion and so length of i-right palindrome is at least as long as length of i-left palindrome.
Case 4:
L[currentRightPosition] > = centerRightPosition – currentRightPosition applies when:
- i-left palindrome is NOT completely contained in center palindrome
Above condition is satisfied when L[currentLeftPosition] > centerRightPosition – currentRightPosition In this case, length of i-right palindrome is at least as long (centerRightPosition – currentRightPosition) and there is a possibility of i-right palindrome expansion. In following figure,
If we take center position 7, then Case 3 applies at currentRightPosition 11 because i-left palindrome at currentLeftPosition 3 is a prefix of center palindrome and i-right palindrome is not suffix of input string, so here L[11] = 9, which is greater than i-left palindrome length L[3] = 3. In the case, it is guaranteed that L[11] will be at least 3, and so in implementation, we 1
st
set L[11] = 3 and then we try to expand it by comparing characters in left and right side starting from distance 4 (As up-to distance 3, it is already known that characters will match). If we take center position 11, then Case 4 applies at currentRightPosition 15 because L[currentLeftPosition] = L[7] = 7 > centerRightPosition – currentRightPosition = 20 – 15 = 5. In the case, it is guaranteed that L[15] will be at least 5, and so in implementation, we 1
st
set L[15] = 5 and then we try to expand it by comparing characters in left and right side starting from distance 5 (As up-to distance 5, it is already known that characters will match). Now one point left to discuss is, when we work at one center position and compute LPS lengths for different rightPositions, how to know that what would be next center position. We change centerPosition to currentRightPosition if palindrome centered at currentRightPosition expands beyond centerRightPosition. Here we have seen four different cases on how LPS length of a position will depend on a previous position's LPS length.
Similar Reads
DSA Tutorial - Learn Data Structures and Algorithms DSA (Data Structures and Algorithms) is the study of organizing data efficiently using data structures like arrays, stacks, and trees, paired with step-by-step procedures (or algorithms) to solve problems effectively. Data structures manage how data is stored and accessed, while algorithms focus on
7 min read
Quick Sort QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a pivot and partitions the given array around the picked pivot by placing the pivot in its correct position in the sorted array. It works on the principle of divide and conquer, breaking down the problem into s
12 min read
Merge Sort - Data Structure and Algorithms Tutorials Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach. It works by recursively dividing the input array into two halves, recursively sorting the two halves and finally merging them back together to obtain the sorted array. Merge
14 min read
Data Structures Tutorial Data structures are the fundamental building blocks of computer programming. They define how data is organized, stored, and manipulated within a program. Understanding data structures is very important for developing efficient and effective algorithms. What is Data Structure?A data structure is a st
2 min read
Bubble Sort Algorithm Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in the wrong order. This algorithm is not suitable for large data sets as its average and worst-case time complexity are quite high.We sort the array using multiple passes. After the fir
8 min read
Breadth First Search or BFS for a Graph Given a undirected graph represented by an adjacency list adj, where each adj[i] represents the list of vertices connected to vertex i. Perform a Breadth First Search (BFS) traversal starting from vertex 0, visiting vertices from left to right according to the adjacency list, and return a list conta
15+ min read
Binary Search Algorithm - Iterative and Recursive Implementation Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(log N). Binary Search AlgorithmConditions to apply Binary Searc
15 min read
Insertion Sort Algorithm Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is like sorting playing cards in your hands. You split the cards into two groups: the sorted cards and the unsorted cards. T
9 min read
Array Data Structure Guide In this article, we introduce array, implementation in different popular languages, its basic operations and commonly seen problems / interview questions. An array stores items (in case of C/C++ and Java Primitive Arrays) or their references (in case of Python, JS, Java Non-Primitive) at contiguous
4 min read
Sorting Algorithms A Sorting Algorithm is used to rearrange a given array or list of elements in an order. For example, a given array [10, 20, 5, 2] becomes [2, 5, 10, 20] after sorting in increasing order and becomes [20, 10, 5, 2] after sorting in decreasing order. There exist different sorting algorithms for differ
3 min read