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?

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"?

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 positioni/ 2. Then initialize the arrayans[i] to zero; this will be the max. length of a palindrome starting at positioni.First iterate through every index

kin Manacher and setans[(k-A[k] + 1) / 2] =A[k]. Then iterate through every indexiin theansarray, keeping track of the highest-index center reached so far. Update the values accordingly.Final runtime:

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

“Online” means that this algorithm knows the longest palindromic substring

endingat any given position. For starting positions simply reverse the input string.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

iI update the info about the longest palindrome starting at positioni-A[i]. However this only works correctly for all starting positions<= N/2whereN = 2*n+1(For Manacher) andnis 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/2and not<= N/2as in the case of the"longest palindrome length starting ati"If anyone is interested, I'm trying to do this because I'm trying to solve

Build a Palindromeon HackerRankEDIT: 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