nagendra.. plz show the working using an example .. take input babbaabbc
On Sun, Sep 6, 2009 at 2:07 PM, Nagendra Kumar <[email protected]>wrote: > > @all: > > T(i,j) : denotes the length of longest palindrome with start index > i and end index j index. > T(i,j )= > max { > 1 , if i == j; > 2+T(i+1,j-1) if x[i] == x[j]; > max(T(i+1,j) T(i,j-1)) > > } > This is the recurrence relation > Now algorithm: > T(i,i-1) = 0 for 1<= i <= n. > > for i= 1 to n > T(i)(i) = 1; > start with the distnace d > for d = 1 to n > for i = 1 to n -d > { j = i+d; > if(x[i] == x[j]) > T[i][j] = 2+ T[i+1][j-1]; > else > T[i][j] = max (T[i+1][j], T[i][j-1]) > > } > > return T[1][n]; > > On Tue, Sep 1, 2009 at 12:01 AM, Dufus<[email protected]> wrote: > > > > This is one of the most difficult dynamic programming problem I have > > faced so far. > > > > A good discussion on this problem and different solutions can be found > > at > > > http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ > > > > _dufus > > > > > > On Aug 31, 6:01 pm, ankur aggarwal <[email protected]> wrote: > >> @abhijeet > >> dryrun on this > >> > >> abbaabba > >> > >> On Mon, Aug 31, 2009 at 5:45 PM, Abhijeet Kumar > >> <[email protected]>wrote: > >> > >> > u can push the string onto a stack ... so last element will be on top > ... > >> > den u can pop out element and compare ... > >> > if u have 2 or more set of palindromes .. > >> > u can keep a counter and keep a check on dat... > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
