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

Правка en1, от 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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский KarimElSheikh 2017-11-19 13:50:30 575 Initial revision (published)