Number of pallindromic prefixes efficiently??

Правка en1, от aman_naughty, 2019-08-23 16:25:03

Can someone suggest some method to count the number of prefixes of a given string which are also palindromes? It would be even helpful if I can get a boolean array of the length of string where a true denotes that a prefix up to this index is a palindrome.

Right now I have simple 2d dp approach where dp[i][j] is true is string i to j is a pallindrome, but this is O(n2). Is therre some O(n) or O(nlog(n)) method thankyou.

Теги palindrome, prefix, kmp, #help

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский aman_naughty 2019-08-23 16:26:42 6
en1 Английский aman_naughty 2019-08-23 16:25:03 474 Initial revision (published)