@ Ankur, IMHO suffix tree is ONE of the solution.
_dufus On Sep 3, 7:37 am, ankur aggarwal <[email protected]> wrote: > only suffix tree is the soln i think.. > > On Wed, Sep 2, 2009 at 11:20 AM, nitin mathur > <[email protected]>wrote: > > > > > > > Hi everybody.. > > > I am sorry as the algorithm I proposed takes O(n^2) and not O(n). But its > > not wrong. > > > @Ankur The algorithm given in cormen is for longest common > > subsequence. But a similar algorithm exists for longest common substring > > too. > > > you can find it following the link > >http://en.wikipedia.org/wiki/Longest_common_substring_problem > > > <http://en.wikipedia.org/wiki/Longest_common_substring_problem>Actually > > these problems (that uses Dynamic Programming approach) are solved in two > > stages. First, we need to build a table and then we need to traverse it in > > particular fashion to retrieve all possible longest common substrings. > > > The second stage takes O(n) time. > > But the preprocessing takes O(n^2) time. > > So, overall it takes O(n^2) time. > > > I believe its worst approach for this problem (as it needs O(n^2) extra > > spaces too). So not needed to discuss more about this approach. Better some > > other method should be discovered. > > > Nitin Mathur --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
