*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 <[email protected]>wrote: > " *Ukkonen's algorithm* is a linear-time, online > algorithm<http://en.wikipedia.org/wiki/Online_algorithm>for constructing > suffix > trees <http://en.wikipedia.org/wiki/Suffix_tree>, proposed by Esko > Ukkonen<http://en.wikipedia.org/w/index.php?title=Esko_Ukkonen&action=edit&redlink=1>in > 1995" > > source: wikipedia > > > On Sun, Sep 23, 2012 at 5:08 PM, Navin Kumar <[email protected]>wrote: > >> 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 <[email protected] >> > wrote: >> >>> Hello everybody, >>> I need to find a way of finding the longest palindrome in a very very >>> long string (n<=20000) . a linear time algo is expected. help me out >>> >>> -- >>> 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/-/JdXOBU9fu34J. >>> 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. > -- *RAHUL KUMAR DUBEY* *BTech-3rd year * *Computer Science &Engineering * *Motilal Nehru National Institute Of Technology* *Allahabad[211004],UP.* -- 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.
