Is it possible to extend Manacher's algorithm to include information about the longest palindromic substring that starts at every position?

Revision en1, by KarimElSheikh, 2017-11-19 13:50:30

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English KarimElSheikh 2017-11-19 13:50:30 575 Initial revision (published)