for finding longest palindrome, you must find all the palindrome in given string. so, it is easy to find all palindrome of given string
for example string="aabbbeaeb" in this string aa, bb, beaeb are palindrome but beaeb is a longest palindrome ________________________________ From: Abhishek Goswami <[email protected]> To: [email protected] Sent: Sunday, 8 May 2011 3:13 PM Subject: Re: [algogeeks] can u please explain me in descriptive manner On Sat, May 7, 2011 at 2:31 PM, Amir hossein Shahriari <[email protected]> wrote: @venkatesan : im not sure about that! this problem is different > > >but we can do it in O(n^2) >the DP1 can be built done in O(n^2) as in abhijith's solution >also the DP2 can be built in O(n^2) too. instead of counting the min # of >palindrome strings that can make the range of [low,high] >count how many palindromes can make the range [0,x] >this makes the dp2 array linear and the overall running time quadratic > > >int minCuts(int x) >{ > if(isPalin(0,x)) return 0; > if(dp2[x]!=-1) return dp2[x]; > int ans=1e9; > for(int i=1;i<high;i++) > if (isPalin(i,x)) > ans=min(ans,1+minCuts(i-1)); > return dp2[x]=ans; >} > > > > > >On Sat, May 7, 2011 at 12:41 PM, venkatesan B <[email protected]> >wrote: > >problem like to find largest palindrome in the string >>so, in O(n) time complexity to find largest palindrome in the string >> >> >> >> >> >>________________________________ >> From: hary rathor <[email protected]> >>To: [email protected] >>Sent: Saturday, 7 May 2011 10:33 AM >>Subject: Re: [algogeeks] >> >> >> >>@venkatesan >> >> >>now you give the algorithm ... of O(n) -- >>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?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 [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?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 [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?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 [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?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 [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?hl=en.
