KarimElSheikh's blog

Is it possible to extend Manacher's algorithm to include information about the longest palindromic substring that starts at every position?
By KarimElSheikh, history, 7 years ago, In English

Is it possible to extend Manacher's algorithm to include information about the longest palindromic substring that starts at every position and still keep the O(N) time complexity?

For example the string cbcbaaabc should give the array [3, 3, 7, 5, 3, 2, 1, 1, 1] which corresponds to the strings cbc, bcb, cbaaabc, baaab, aaa, aa, a, b, c respectively

What about an O(NlogN) solution?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can add an extra step after Manacher's algorithm: you're looking for a palindromic substring starting at a specific position with the rightmost center (it's same same as the longest one). After that you only have to solve a data structure problem like "values on that segment should be at least X; what is the resulting value in each point"?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You may be interested in this csacademy problem, which gives the exact opposite transformation.

A simple modification of the approach in that problem will work. After running Manacher, say we have an array A[i] of the maximum lengths of palindromes centered at position i / 2. Then initialize the array ans[i] to zero; this will be the max. length of a palindrome starting at position i.

First iterate through every index k in Manacher and set ans[(k - A[k] + 1) / 2] = A[k]. Then iterate through every index i in the ans array, keeping track of the highest-index center reached so far. Update the values accordingly.

Final runtime: O(n).

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This blogpost mentions (and gives link to implementation for) online version of the algorithm due to Mikhail Rubinchik: http://codeforces.net/blog/entry/12143

“Online” means that this algorithm knows the longest palindromic substring ending at any given position. For starting positions simply reverse the input string.

→ Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I coded a solution but I'm not sure it's correct, the main idea is: During Manacher's runtime whenever Manacher's array is updated for the palindrome centered around position i I update the info about the longest palindrome starting at position i-A[i]. However this only works correctly for all starting positions <= N/2 where N = 2*n+1 (For Manacher) and n is the length of the string, maybe someone can prove this. To solve this I did another Manacher traversal but in reverse from the end to the beginning, this time I update the longest palindrome for starting positions >= N/2.

In the same way I also generate the longest palindrome length ending at position i, also during the first Manacher pass, this only works correctly for indices >= N/2 and not <= N/2 as in the case of the "longest palindrome length starting at i"

If anyone is interested, I'm trying to do this because I'm trying to solve Build a Palindrome on HackerRank

EDIT: my code fails in some cases and there'a bug in the second portion of the Manacher function I have to try ekzhang's solution

→ Reply