Re: [algogeeks] longest palindrome in a string size 2*10^4

@rahul: excellent answer. thanks a ton!!. @navin :i will try that too .Thanks !! -- 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 a

Re: [algogeeks] longest palindrome in a string size 2*10^4

http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html: linear time On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman wrote: > Hello everybody, > I need to find a way of finding the longest palindrome in a very very long > string (n<=2) . a linear time algo is expected. help m

Re: [algogeeks] longest palindrome in a string size 2*10^4

*Manacher's algorithm * * * *Its a famous algorithm for finding longest palindrome in a string in O(n)* *have a look at it on internet ...* *http://www.leetcode.com/2011/11/longest-palindromic-substring-part-ii.html* see if it can help you .. On Sun, Sep 23, 2012 at 5:29 PM, Navin Kumar wrote: >

Re: [algogeeks] longest palindrome in a string size 2*10^4

" *Ukkonen's algorithm* is a linear-time, online algorithmfor constructing suffix trees , proposed by Esko Ukkonenin 1995" source:

Re: [algogeeks] longest palindrome in a string size 2*10^4

Build a common suffix tree for the given string and for its reverse. Then take out the string ending at maximum depth at a common node. Time complexity would be linear. On Sat, Sep 22, 2012 at 5:33 PM, Aditya Raman wrote: > Hello everybody, > I need to find a way of finding the longest palindrome

Re: [algogeeks] Longest palindrome

you can do it in O(n) if you can give extra memory 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@goo

Re: [algogeeks] Longest palindrome

Use DP, read the algorithm "Edit distance" and modificated to get max palim. 2011/8/21 anurag saxena > 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 r

Re: [algogeeks] Longest palindrome

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

Re: [algogeeks] Longest palindrome

dp will work fine. :-) O(n^2) algo. -- 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 mo

Re: [algogeeks] Longest palindrome

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 st

Re: [algogeeks] Longest palindrome

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. > >

Re: [algogeeks] Longest palindrome

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

Re: [algogeeks] Longest Palindrome

The blogsite referred is unavailable. On Fri, Dec 31, 2010 at 3:49 AM, Anand wrote: > > http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html > > > 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

Re: [algogeeks] Longest Palindrome

http://anandtechblog.blogspot.com/2010/06/find-longest-palindromic-substring-in.html 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 > "Algor

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

I don't understand how to constuct the suffix tree in less than O(n^2) can anyone explain me this? On Tue, Jul 6, 2010 at 10:03 AM, Jitendra Kushwaha wrote: > @Ankit Narang > Think about your algo it is not a O(n). First of all you wont get > solution comparing start of str1 and end of str2 >

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

@Ankit Narang Think about your algo it is not a O(n). First of all you wont get solution comparing start of str1 and end of str2 Their is solution in O(n) other than suffix tree Here is the link http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ -- Regard

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

refer http://www.allisons.org/ll/AlgDS/Tree/Suffix/ this would be at most O(n) Best Regards Ashish Goel "Think positive and find fuel in failure" +919985813081 +919966006652 On Mon, Jul 5, 2010 at 10:45 PM, vijay wrote: > Longest palindrome in a given str (less than O(n^2) ) > > i think we

Re: [algogeeks] Longest palindrome in a given str (less than O(n^2) )

make a generalised suffix tree of str and reverse of str then for every two nodes find the longest common prefix On Mon, Jul 5, 2010 at 10:45 PM, vijay wrote: > Longest palindrome in a given str (less than O(n^2) ) > > i think we should use suffix tree. does anyone know the algo\logic? > > -- >