Suffix tree is obviously there but 1. It requires more lots of space. Just draw a suffix tree and you will know. 2. Pre-processing takes time. We cant ignore this time because its proportional to N.
There is one linear solution described here: http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ Still trying to understand O(N) algo.. On Sun, Jun 6, 2010 at 2:15 PM, jalaj jaiswal <[email protected]> wrote: > i think it can be done in O(n) using suffix trees. > but making suffix tree also requires O(n) space and O(n) time... > attached is the ppt (it has the same example)... > > > > On Sun, Jun 6, 2010 at 1:51 PM, Rohit Saraf <[email protected]> > wrote: >> >> but actually we need something better as per prob, >> cannot be done in O(n). >> so we need to think of something like O(n lg n) or O( n ^ 3/2) :) >> >> -------------------------------------------------- >> Rohit Saraf >> Second Year Undergraduate, >> Dept. of Computer Science and Engineering >> IIT Bombay >> http://www.cse.iitb.ac.in/~rohitfeb14 >> >> -- >> 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. > > > > -- > With Regards, > Jalaj Jaiswal > +919026283397 > B.TECH IT > IIIT ALLAHABAD > > -- > 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.
