I know that is not the best solution but here we go: p [i] [j] = 1 if s [i.. j] is palindrome, 0 otherwise
p [i] [i] = 1 p [i] [i +1] = s [i] == s [i +1] p [i] [k] = s [i] == s [k] & & p [i +1] [k-1], k> i +1 time complexity = O (n ^ 2) Space complexity = O (n ^ 2) You can modify the algorithm to use only O (n) space using only the diagonal matrix Wladimir Araujo Tavares *Federal University of Ceará * On Thu, Jun 23, 2011 at 1:06 PM, Anand <anandut2...@gmail.com> wrote: > > http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html > > > On Wed, Jun 22, 2011 at 9:28 PM, Avinash <dongre.avin...@gmail.com> wrote: > >> http://stevekrenzel.com/articles/longest-palnidrome >> But for some reason it is failing for string "ISAAS", may be my >> understanding is incorrect. >> >> >> Thanks >> Avinash >> http://avi-programming-blog.blogspot.com/ >> >> >> On Jun 21, 11:31 pm, Swathi <chukka.swa...@gmail.com> wrote: >> > Does any one know how to return the "Longest palindrome in a string in >> > O(n)". >> > From googling i found that we can use suffix trees but there is no code. >> I >> > am looking for logic and also for running code. >> > >> > Thanks, >> > Swathi >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
