Re: [algogeeks] Re: longest palindrome
Regarding the explanation of the suffix tree method, here is the link: http://algo2006.csie.dyu.edu.tw/paper/2/A24.pdf On Tue, Jan 24, 2012 at 8:05 PM, Ashish Goel wrote: > http://www.akalin.cx/longest-palindrome-linear-time > > lovely explanation.. > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > > > On Tue, Jan 24, 2012 at 7:52 PM, Ashish Goel wrote: > >> while suffix tree of str and reverse(str) and finding deepst fork to get >> the palindrome works, there is a solution available at >> http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html >> which is O(n). Can anyone explain this, a bit complex for me. >> >> Best Regards >> Ashish Goel >> "Think positive and find fuel in failure" >> +919985813081 >> +919966006652 >> > > -- > 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.
[algogeeks] Re: longest palindrome
http://www.akalin.cx/longest-palindrome-linear-time lovely explanation.. Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Tue, Jan 24, 2012 at 7:52 PM, Ashish Goel wrote: > while suffix tree of str and reverse(str) and finding deepst fork to get > the palindrome works, there is a solution available at > http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html > which is O(n). Can anyone explain this, a bit complex for me. > > Best Regards > Ashish Goel > "Think positive and find fuel in failure" > +919985813081 > +919966006652 > -- 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.
[algogeeks] Re: Longest palindrome
sorry, I meant to joke about (0.5 * n^2) ;P On Aug 22, 4:46 pm, "icy`" wrote: > brute force... http://codepad.org/D07BNo91 There are some > checks to help reduce O(n^2), so I want to say.. O(1.5n) ? =) > > #output for str = 'abaccddccefe' > #ccddcc 6 > > #for str = 'abraxyzarba' > #a 1 > > On Aug 22, 1:09 pm, uma wrote: > > > > > > > > > can yo tell exactly , how the suffix tree is used for finding > > palindromes? > > > On Aug 22, 3:58 am, WgpShashank wrote: > > > > Hey Geeks I think question can be solved by many ways . some of the > > > algorithms are i have implemented & aware of are -> > > > > 1st. Algo > > > Generate all palindromes (even & odd length ) of given string while keep > > > tracking of their length in last just compare max (evenlength_palindrome , > > > oddlength_palindrome) . > > > Time Complexity O(N^2) where N is length of String > > > > 2nd . Algo. For Those Who are just saying Use DP :) > > > Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of > > > String (say s2) ) It Involves > > > DP to solve efficiently but guaranteed optimal solution > > > Time Complexity O(N^2) where N is length of String > > > Space Complexity O(N^2) for table > > > > 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the > > > suffix tree of string & reverse string check no every node where suffix > > > belongs to , the deepest common node will us longest palindrome in given > > > string. > > > > Correct me if i missed something ? > > > > Thanks > > > Shashank Mani > > > Computer Science > > > Birla Institute of Technology ,Mesra -- 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.
[algogeeks] Re: Longest palindrome
brute force...http://codepad.org/D07BNo91 There are some checks to help reduce O(n^2), so I want to say.. O(1.5n) ?=) #output for str = 'abaccddccefe' #ccddcc 6 #for str = 'abraxyzarba' #a 1 On Aug 22, 1:09 pm, uma wrote: > can yo tell exactly , how the suffix tree is used for finding > palindromes? > > On Aug 22, 3:58 am, WgpShashank wrote: > > > > > > > > > Hey Geeks I think question can be solved by many ways . some of the > > algorithms are i have implemented & aware of are -> > > > 1st. Algo > > Generate all palindromes (even & odd length ) of given string while keep > > tracking of their length in last just compare max (evenlength_palindrome , > > oddlength_palindrome) . > > Time Complexity O(N^2) where N is length of String > > > 2nd . Algo. For Those Who are just saying Use DP :) > > Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of > > String (say s2) ) It Involves > > DP to solve efficiently but guaranteed optimal solution > > Time Complexity O(N^2) where N is length of String > > Space Complexity O(N^2) for table > > > 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the > > suffix tree of string & reverse string check no every node where suffix > > belongs to , the deepest common node will us longest palindrome in given > > string. > > > Correct me if i missed something ? > > > Thanks > > Shashank Mani > > Computer Science > > Birla Institute of Technology ,Mesra -- 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.
[algogeeks] Re: Longest palindrome
can yo tell exactly , how the suffix tree is used for finding palindromes? On Aug 22, 3:58 am, WgpShashank wrote: > Hey Geeks I think question can be solved by many ways . some of the > algorithms are i have implemented & aware of are -> > > 1st. Algo > Generate all palindromes (even & odd length ) of given string while keep > tracking of their length in last just compare max (evenlength_palindrome , > oddlength_palindrome) . > Time Complexity O(N^2) where N is length of String > > 2nd . Algo. For Those Who are just saying Use DP :) > Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of > String (say s2) ) It Involves > DP to solve efficiently but guaranteed optimal solution > Time Complexity O(N^2) where N is length of String > Space Complexity O(N^2) for table > > 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the > suffix tree of string & reverse string check no every node where suffix > belongs to , the deepest common node will us longest palindrome in given > string. > > Correct me if i missed something ? > > Thanks > Shashank Mani > Computer Science > Birla Institute of Technology ,Mesra -- 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.
Re: [algogeeks] Re: Longest palindrome
@ harry how it is possible man On Mon, Aug 22, 2011 at 3:58 AM, WgpShashank wrote: > Hey Geeks I think question can be solved by many ways . some of the > algorithms are i have implemented & aware of are -> > > 1st. Algo > Generate all palindromes (even & odd length ) of given string while keep > tracking of their length in last just compare max (evenlength_palindrome , > oddlength_palindrome) . > Time Complexity O(N^2) where N is length of String > > 2nd . Algo. For Those Who are just saying Use DP :) > Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of > String (say s2) ) It Involves > DP to solve efficiently but guaranteed optimal solution > Time Complexity O(N^2) where N is length of String > Space Complexity O(N^2) for table > > 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the > suffix tree of string & reverse string check no every node where suffix > belongs to , the deepest common node will us longest palindrome in given > string. > > Correct me if i missed something ? > > Thanks > Shashank Mani > Computer Science > Birla Institute of Technology ,Mesra > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/56GQiQVlUukJ. > > 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.
[algogeeks] Re: Longest palindrome
Hey Geeks I think question can be solved by many ways . some of the algorithms are i have implemented & aware of are -> 1st. Algo Generate all palindromes (even & odd length ) of given string while keep tracking of their length in last just compare max (evenlength_palindrome , oddlength_palindrome) . Time Complexity O(N^2) where N is length of String 2nd . Algo. For Those Who are just saying Use DP :) Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of String (say s2) ) It Involves DP to solve efficiently but guaranteed optimal solution Time Complexity O(N^2) where N is length of String Space Complexity O(N^2) for table 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the suffix tree of string & reverse string check no every node where suffix belongs to , the deepest common node will us longest palindrome in given string. Correct me if i missed something ? Thanks Shashank Mani Computer Science Birla Institute of Technology ,Mesra -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/56GQiQVlUukJ. 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.
[algogeeks] Re: Longest palindrome
So, suggest some approach plz for this ques. On Aug 22, 12:59 am, Dave wrote: > @Sanjay: Will method 1 really work? What would it return on the string > "abraxyzarba"? The longest common substring between this string and > its reverse is "abra", but how does that relate to the fact that the > longest palindrome is any single letter of the string? What am I > missing? > > Dave > > On Aug 21, 1:46 pm, anurag saxena wrote: > > > > > > > > > method 1) : we can reverse the string and find the longest common > > substring occurring in reversed string and original string. > > > method 2) : making a generalized suffix tree of string and reversed > > string and each node should depict whether the suffix belongs to > > string or reversed string .. then the deepest node having both the > > marker will be longest palindrome. > > > On 8/21/11, Sanjay Rajpal wrote: > > > > i hvn't read about suffix trees. will u plz post a useful link ? > > > > Sanju > > > :) > > > > On Sun, Aug 21, 2011 at 11:21 AM, MAC wrote: > > > >> suffix tree will solve it . > > > >> On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh < > > >> love.for.programm...@gmail.com> wrote: > > > >>> how abt goimg with brute force?? check starting from first character if > > >>> first 2 chars frm a palin, then chck if first 3 form a palin... continue > > >>> until the end of string. > > > >>> Now starting from 2nd char, do the same. > > > >>> keep a var max to store the max value. > > > >>> -- > > >>> 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. > > > >> -- > > >> thanks > > >> --mac > > > >> -- > > >> 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.-Hide quoted text - > > > - Show quoted text - -- 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.
[algogeeks] Re: Longest palindrome
@Sanjay: Will method 1 really work? What would it return on the string "abraxyzarba"? The longest common substring between this string and its reverse is "abra", but how does that relate to the fact that the longest palindrome is any single letter of the string? What am I missing? Dave On Aug 21, 1:46 pm, anurag saxena wrote: > method 1) : we can reverse the string and find the longest common > substring occurring in reversed string and original string. > > method 2) : making a generalized suffix tree of string and reversed > string and each node should depict whether the suffix belongs to > string or reversed string .. then the deepest node having both the > marker will be longest palindrome. > > On 8/21/11, Sanjay Rajpal wrote: > > > > > i hvn't read about suffix trees. will u plz post a useful link ? > > > Sanju > > :) > > > On Sun, Aug 21, 2011 at 11:21 AM, MAC wrote: > > >> suffix tree will solve it . > > >> On Sun, Aug 21, 2011 at 11:46 PM, priya ramesh < > >> love.for.programm...@gmail.com> wrote: > > >>> how abt goimg with brute force?? check starting from first character if > >>> first 2 chars frm a palin, then chck if first 3 form a palin... continue > >>> until the end of string. > > >>> Now starting from 2nd char, do the same. > > >>> keep a var max to store the max value. > > >>> -- > >>> 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. > > >> -- > >> thanks > >> --mac > > >> -- > >> 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.- Hide quoted text - > > - Show quoted text - -- 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.
[algogeeks] Re: Longest Palindrome
Manacher's algorithm does. I think it's a variant of Z algorithm. On Dec 31 2010, 5:10 am, Aniket wrote: > How do you find the longest palindrome in a given string in O(n) time? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Longest Palindrome
@Anand post correct algorithm. There is no simpler method to find longest palindrome in a linear time. To understand the algorithm you may be should know the Z algorithm cause main idea is the same. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Re: Longest Palindrome
@Anand:I went through the link posted in your blog.But I found the method little bit hard to understand. @Aviral:Please elaborate the approach or give some link as in your blog I didn't find the solution. It will be very helpful.Thanks in advance. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.
[algogeeks] Re: Longest Palindrome
Use suffix tree ... http://coders-stop.blogspot.com/2010/11/suffix-trees.html On Dec 31 2010, 3:19 am, Anand wrote: > http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-su... > > On Thu, Dec 30, 2010 at 1:10 PM, Aniket wrote: > > How do you find the longest palindrome in a given string in O(n) time? > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algoge...@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 algoge...@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.
