Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Number of pallindromic prefixes efficiently??
Difference between en1 and en2, changed 6 character(s)
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 isf string i to j is a pallindrome, but this is O(n2).↵
Is ther
re some O(n) or O(nlog(n)) method thankyou.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English aman_naughty 2019-08-23 16:26:42 6
en1 English aman_naughty 2019-08-23 16:25:03 474 Initial revision (published)